让我们介绍一些稍后需要的定义。
令 $$$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)$$$ 为 $$$prime(x)$$$ 中所有 $$$p$$$ 的 $$$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)}$$$。
输入
唯一一行包含整数 $$$x$$$ 和 $$$n$$$ ($$$2 \le x \le 10^{9}$$$, $$$1 \le n \le 10^{18}$$$) - 公式中使用的数字。
输出
打印答案。
示例
输入 #1
10 2
输出 #1
2
输入 #2
20190929 1605
输出 #2
363165664
输入 #3
947 987654321987654321
输出 #3
593574252
注意
在第一个示例中,$$$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)$$$ 的答案。
在第三个示例中,请注意溢出问题。