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)=213051=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)=325071=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 (2x1092≤x≤109, 1n10181≤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.597101711.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;
} 
02-11 10:38