Primes and Multiplication
题意翻译
首先先介绍一些涉及到的定义:
定义$prime(x)$表示x的质因子集合。举例来说,$prime(140) = \{2, 5, 7\}$,$prime(169) = \{13\}$。
定义$g(x, p)$表示存在一个最大的$k \in N^*$,使得x可以被$p^k$整除(即$p^k | x \ \&\ p^{k+1}\nmid x$),那么$g(x, p) = 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)$表示所有$g(y, p)~~(p \in prime(x))$的乘积,举例来说:
- $f(30, 70) = g(70,2)·g(70,3)·g(70, 5) = 2^1·3^0·5^1 = 10$
- $f(525,63) = g(63,3)·g(63,5)·g(63,7) = 3^2·5^0·7^1 = 63$
现在给出两个整数$x$和$n$,请计算出$f(x,1)·f(x,2)\dots f(x,n)~mod~(10^9+7)$的值。
题目描述
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)} $ .
输入输出格式
输入格式
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.
输入输出样例
输入样例 #1
10 2
输出样例 #1
2
输入样例 #2
20190929 1605
输出样例 #2
363165664
输入样例 #3
947 987654321987654321
输出样例 #3
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.