F

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

Input

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

Output

The only line of the output will contain S modulo 9901.

Sample Input

2 3

Sample Output

Hint

2^3 = 8.
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).

首先这个a^b十分的大

我们不可能每一个单独找那么复杂度一定是巨大的

所有我们们肯定自然的想到唯一分解定理

也就是把所有的数全部分解成质数和指数的形式

根据组合数学

我们把所有质数的所有指数组合相乘就是答案了

即所有的 $p^{0}+p^{1}+p^{2}+...+pb*a{_{n}}^{}$ 累乘

那么我就也能把它看作x个等比数列累乘

需要注意的是等比数列的取模问题

我们可以选择使用逆元，但是分母若是跟mod不为互质，就无法使用逆元

根据 $frac{a}{b}modc=frac{amod(b*c))}{b}modc$ 可求

注意的是b*c可能大于1e9计算a可能会炸int64

所以避免乘法使用快速加法即可

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
const long long mod=9901;
vector<pair<long long,long long> > ve;
inline long long  mult_mod(long long a,long long b, long long m)
{
    long long res = 0;
    while(b){
        if(b&1) res = (res+a)%m;
        a = (a+a)%m;
        b >>= 1;
    }
    return res;
}
long long quick_pow(long long a,long long b,long long c)
{
    long long ans=1;
    while(b)
    {
        if(b%2==1) ans=mult_mod(ans, a, c);
        b/=2;
        a=mult_mod(a,a,c);
    }
    return ans;
}
//long long inv(long long b)
//{
//    return quick_pow(b,mod-2);
//}
int main()
{
    long long a,b;
    cin>>a>>b;
    if(a==0)
    {
        cout<<"0"<<endl;
        return 0;
    }
    long long tmp=a;
    for(long long  i=2;i*i<=a;i++)
    {
        long long num=0;
        while(tmp%i==0)
        {
            tmp/=i;
            num++;
        }
        if(num) ve.push_back(make_pair(i,num));
    }
    if(tmp!=1) ve.push_back(make_pair(tmp,1));
    long long ans=1;
    for(int i=0;i<ve.size(); i++)
    {
        long long tmp;
        long long p=ve[i].second;
        long long q=ve[i].first;
        long long tmpmod=mod*(q-1);
        //cout<<p<<" "<<q<<endl;
        tmp=(((quick_pow(q,p*b+1,tmpmod)) + tmpmod-1)%tmpmod)/(q-1)%mod ;
        //cout<<tmp<<endl;
        ans=(ans*tmp)%mod;
    }
    cout<<ans<<endl;
}