Sumdiv

You are given two natural numbers A and B. Let S be the sum of all natural divisors of $A^B$.

Task

Find S modulo 1 000 000 007.

Input data

The first line of the input file sumdiv.in contains the two numbers A and B, separated by at least one space.

Output data

The first line of the output file sumdiv.out will contain S modulo 1 000 000 007.

Constraints

• $1 \le A \le 10^{12}$
• $0 \le B \le 10^{18}$

Example

sumdiv.in

2 3

sumdiv.out

15

Explanation

$2^3 = 8$.
The natural divisors of 8 are: 1, 2, 4, 8. Their sum is 15.