CF1228C.Primes and Multiplication

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:

• $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)}$.

我们先引入一些后续需要用到的定义。

设 $prime(x)$ 表示 $x$ 的所有质因数构成的集合。例如，$prime(140) = \{ 2, 5, 7 \}$，$prime(169) = \{ 13 \}$。

设 $g(x, p)$ 表示形如 $p^k$（其中 $k$ 为非负整数）的最大整数，使得 $x$ 能被 $p^k$ 整除。例如：

• $g(45, 3) = 9$（因为 $45$ 能被 $3^2 = 9$ 整除，但不能被 $3^3 = 27$ 整除），
• $g(63, 7) = 7$（因为 $63$ 能被 $7^1 = 7$ 整除，但不能被 $7^2 = 49$ 整除）。

设 $f(x, y)$ 表示对所有 $p \in prime(x)$，将 $g(y, p)$ 相乘所得的乘积。例如：

• $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$。

给定整数 $x$ 和 $n$，请计算 $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.

唯一的一行包含整数 $x$ 和 $n$（$2 \le x \le 10^{9}$，$1 \le n \le 10^{18}$）——公式中使用的数字。

Print the answer.

输出答案。

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.

在第一个例子中，$f(10, 1) = g(1, 2) \cdot g(1, 5) = 1$，$f(10, 2) = g(2, 2) \cdot g(2, 5) = 2$。

在第二个例子中，公式的实际值约为 $1.597 \cdot 10^{171}$。请确保输出答案对 $(10^{9} + 7)$ 取模的结果。

在第三个例子中，请注意溢出问题。