C. Primes and Multiplicationtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet's introduce some definitions that will be needed later.Let prime(x) be the set of prime divisors of x. For example, prime(140) = \{ 2, 5, 7 \}, prime(169) = \{ 13 \}.Let g(x, p) be the maximum possible integer p^k where k is an integer such that x is divisible by p^k. For example:  g(45, 3) = 9 (45 is divisible by 3^2=9 but not divisible by 3^3=27),  g(63, 7) = 7 (63 is divisible by 7^1=7 but not divisible by 7^2=49). Let f(x, y) be the product of g(y, p) for all p in prime(x). For example:  f(30, 70) = g(70, 2) \cdot g(70, 3) \cdot g(70, 5) = 2^1 \cdot 3^0 \cdot 5^1 = 10,  f(525, 63) = g(63, 3) \cdot g(63, 5) \cdot g(63, 7) = 3^2 \cdot 5^0 \cdot 7^1 = 63. You have integers x and n. Calculate f(x, 1) \cdot f(x, 2) \cdot \ldots \cdot f(x, n) \bmod{(10^{9} + 7)}.InputThe only line contains integers x and n (2 \le x \le 10^{9}, 1 \le n \le 10^{18}) — the numbers used in formula.OutputPrint the answer.ExamplesInput
10 2
Output
2
Input
20190929 1605
Output
363165664
Input
947 987654321987654321
Output
593574252
NoteIn the first example, f(10, 1) = g(1, 2) \cdot g(1, 5) = 1, f(10, 2) = g(2, 2) \cdot g(2, 5) = 2.In the second example, actual value of formula is approximately 1.597 \cdot 10^{171}. Make sure you print the answer modulo (10^{9} + 7).In the third example, be careful about overflow issue.
10 2

2 
['math', 'number theory', '*1700']