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

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

Let prime(x)">prime(x)prime(x) be the set of prime divisors of x">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}.

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

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

Let f(x,y)">f(x,y)f(x,y) be the product of g(y,p)">g(y,p)g(y,p) for all p">pp in prime(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 integers x">xx and n">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)f(x,1)?f(x,2)?…?f(x,n)mod(109+7).

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

Print the answer.

10 2

2

20190929 1605

363165664

947 987654321987654321

593574252

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 approximately 1.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
#include
#include
#include
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){
        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<endl;
}