← 返回题目列表

Codeforces · 1228/C

C. 素数和乘法

中文机器翻译题面 查看原题

让我们介绍一些稍后需要的定义。

令 $$$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)$$$ 的答案。

在第三个示例中,请注意溢出问题。