C. 如何防止数学中的质数运算爆精度？

本文共计1813个文字，预计阅读时间需要8分钟。

C. +素数与乘法时间限制+每测试1秒+内存限制每测试256兆字节+输入标准输入+输出标准输出+让我们介绍一些稍后需要的定义。+设p+r+i+m+e+（+x+）+>+p+r+i+m+e+（+x+）+p+。

C. Primes and Multiplication time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Let‘s introduce some definitions that will be needed later.

Letprime(x)">prime(x)prime(x)be the set of prime divisors ofx">xx. For example,prime(140)={2,5,7}">prime(140)={2,5,7}prime(140)={2,5,7},prime(169)={13}">prime(169)={13}prime(169)={13}.

Letg(x,p)">g(x,p)g(x,p)be the maximum possible integerpk">pkpkwherek">kkis an integer such thatx">xxis divisible bypk">pkpk. For example:

• g(45,3)=9">g(45,3)=9g(45,3)=9(45">4545is divisible by32=9">32=932=9but not divisible by33=27">33=2733=27),
• g(63,7)=7">g(63,7)=7g(63,7)=7(63">6363is divisible by71=7">71=771=7but not divisible by72=49">72=4972=49).

Letf(x,y)">f(x,y)f(x,y)be the product ofg(y,p)">g(y,p)g(y,p)for allp">ppinprime(x)">prime(x)prime(x). For example:

• f(30,70)=g(70,2)⋅g(70,3)⋅g(70,5)=21⋅30⋅51=10">f(30,70)=g(70,2)⋅g(70,3)⋅g(70,5)=21⋅30⋅51=10f(30,70)=g(70,2)⋅g(70,3)⋅g(70,5)=21⋅30⋅51=10,
• f(525,63)=g(63,3)⋅g(63,5)⋅g(63,7)=32⋅50⋅71=63">f(525,63)=g(63,3)⋅g(63,5)⋅g(63,7)=32⋅50⋅71=63f(525,63)=g(63,3)⋅g(63,5)⋅g(63,7)=32⋅50⋅71=63.

You have integersx">xxandn">nn. Calculatef(x,1)⋅f(x,2)⋅…⋅f(x,n)mod(109+7)">f(x,1)⋅f(x,2)⋅…⋅f(x,n)mod(109+7)f(x,1)⋅f(x,2)⋅…⋅f(x,n)mod(109+7).

Input

The only line contains integersx">xxandn">nn(2≤x≤109">2≤x≤1092≤x≤109,1≤n≤1018">1≤n≤10181≤n≤1018)— the numbers used in formula.

Output

Print the answer.

Examples input Copy

10 2 output Copy

2 input Copy

20190929 1605 output Copy

363165664 input Copy

947 987654321987654321 output Copy

593574252 Note

In the first example,f(10,1)=g(1,2)⋅g(1,5)=1">f(10,1)=g(1,2)⋅g(1,5)=1f(10,1)=g(1,2)⋅g(1,5)=1,f(10,2)=g(2,2)⋅g(2,5)=2">f(10,2)=g(2,2)⋅g(2,5)=2f(10,2)=g(2,2)⋅g(2,5)=2.

In the second example, actual value of formula is approximately1.597⋅10171">1.597⋅101711.597⋅10171. Make sure you print the answer modulo(109+7)">(109+7)(109+7).

In the third example, be careful about overflow issue.

#include<iostream> #include<stdio.h> #include<algorithm> #include<math.h> using namespace std; typedef unsigned long long ll; ll fac[10050], num;//素因数,素因数的个数 const ll mod=1e9+7; ll pow_mod(ll a, ll n, ll m) { if(n == 0) return 1; ll x = pow_mod(a, n/2, m); ll ans = (ll)x * x % m; if(n % 2 == 1) ans = ans *a % m; return (ll)ans; } void init(ll n) {//唯一分解定理 num = 0; ll cpy = n; ll m = (int)sqrt(n + 0.5); for (int i = 2; i <= m; ++i) { if (cpy % i == 0) { fac[num++] = i; while (cpy % i == 0) cpy /= i; } } if (cpy > 1) fac[num++] = cpy; } int main(){ ll x,n; cin>>x>>n; init(x); ll ans=1; for(ll i=0;i<num;i++){ for(ll cur=fac[i];;cur*=fac[i]){ ans=ans*pow_mod(fac[i],n/cur,mod)%mod; if(cur>n/fac[i]) break; } } cout<<ans%mod<<endl; }