C. Primes and Multiplication（数学）（防止爆精度）

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.

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

Let g(x,p)g(x,p) be the maximum possible integer pkpk where kk is an integer such that xx is divisible by pkpk. For example:

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

Let f(x,y)f(x,y) be the product of g(y,p)g(y,p) for all pp in prime(x)prime(x). For example:

• 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=63f(525,63)=g(63,3)⋅g(63,5)⋅g(63,7)=32⋅50⋅71=63.

You have integers xx and nn. Calculate 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 integers xx and nn (2≤x≤1092≤x≤109, 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)=1f(10,1)=g(1,2)⋅g(1,5)=1, 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 approximately 1.597⋅101711.597⋅10171. Make sure you print the answer modulo (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;
}