84pts玄关求条！

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=9901;
int a,b,ans=1;
int qpow(int j,int p){
    int sum=1;
    while(p>0){
        if(p%2!=0) sum=sum*j%mod;
        j=j*j%mod;
        p=p>>1;
    }
    return sum;
}
int ppp(int x,int y){
    if(x==0) return 1;
    else if(x%2==1) return ppp(x/2,y)*(1+qpow(y,x/2+1))%mod;
    else return (ppp(x/2-1,y)*(1+qpow(y,x/2+1))+qpow(y,x/2))%mod;

}
signed main() {
    cin>>a>>b;
    for(int i=2;i*i<=a;i++){
        if(a%i==0){
            int s=0;
            while(a%i==0) s++,a/=i;
            ans=(ans*ppp(s*b,i))%mod;
        }
    }
    if(a!=0) ans=(ans*ppp(b,a))%mod;
    cout<<ans%9901;

    return 0;
}

WA on 15