2

救命

#include<bits/stdc++.h>
using namespace std;
int a,b,z[100],m=0,zz[100];
long long ans=1,ans1=1,ans2=0,ans3=0;
bool v[50000010];
int s[6000100], cnt = 0;
void w(int n){
    v[1]=1;
    for(int i=2;i<=n;i++){
        if(v[i]==0){
            s[++cnt]=i;
        }
//      cout << i << endl;
        for(int j=1;j<=cnt&&s[j]*i<=n;j++){
            v[i*s[j]]=1;
            if(i%s[j]==0){
                break;
            }
        } 
    }
}
int main(){
    w(50000000);
    cin>>a>>b;
    if(v[a]==0){
        for(int i=0;i<=b;i++){
            ans2=ans2+pow(a,i);
            ans2%=9901;
        }
        cout<<ans2%9901;
        return 0;
    }
    for(int i=2;i<=a;i++){
        while(a%i==0&&v[i]==0){
            z[i]++;
            zz[++m]=i;
            a/=i;
        }
    }
    for(int i=1;i<=m;i++){
        if(z[zz[i]]>1){
            for(int j=1;j<=z[zz[i]]*b;j++){
                while(j>0){
                    if(j%2!=0){
                        ans1=ans1*zz[i]%9901;
                    }
                    zz[i]=zz[i]*zz[i]%9901;
                    j=j>>1;
                }
                ans3+=ans1;
                ans3=ans3%9901;
            }
        }
        if(z[zz[i]]==1) {
            for(int j=1;j<=b;j++){
                while(j>0){
                    if(j%2!=0){
                        ans1=ans1*zz[i]%9901;
                    }
                    zz[i]=zz[i]*zz[i]%9901;
                    j=j>>1;
                }
                ans3+=ans1;
                ans3=ans3%9901;
            }
        }
        ans*=ans3;
        ans%=9901;
    }

    cout<<ans;
    return 0;
}