Codeforces Round 589 (Div. 2) |
---|
Finished |
Let'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:
Let $$$f(x, y)$$$ be the product of $$$g(y, p)$$$ for all $$$p$$$ in $$$prime(x)$$$. For example:
You have integers $$$x$$$ and $$$n$$$. Calculate $$$f(x, 1) \cdot f(x, 2) \cdot \ldots \cdot f(x, n) \bmod{(10^{9} + 7)}$$$.
The only line contains integers $$$x$$$ and $$$n$$$ ($$$2 \le x \le 10^{9}$$$, $$$1 \le n \le 10^{18}$$$) — the numbers used in formula.
Print the answer.
10 2
2
20190929 1605
363165664
947 987654321987654321
593574252
In 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.
Name |
---|