POJ 1845

#include<cstdio>
#include<cstring>
#ifdef unix
#define LL "%lld"
#else
#define LL "%I64d"
#endif
#define mod 9901 
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll tot,c[N/3],prime[N/3];
bool check[N]={1,1};
void get_prime(){
    ll n=10010;
    for(ll i=2;i<=n;i++){
        if(!check[i]) prime[++tot]=i;
        for(ll j=1;j<=tot&&i*prime[j]<=n;j++){
            check[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
ll mul(ll a,ll p,ll M){
    ll res=0;
    for(;p;p>>=1,a=(a+a)%M) if(p&1) res=(res+a)%M;
    return res;
}
ll fpow(ll a,ll p,ll M){
    ll res=1;
    for(;p;p>>=1,a=mul(a,a,M)) if(p&1) res=mul(res,a,M);
    return res;
}
void factor(ll A,ll B){
    ll ans=1;
    for(ll i=1;prime[i]*prime[i]<=A;i++){
        if(A%prime[i]==0){
            ll num=0;
            while(A%prime[i]==0) num++,A/=prime[i];
            ll MOD=(prime[i]-1)*mod;
            ans*=(fpow(prime[i],num*B+1,MOD)+MOD-1)/(prime[i]-1);
            ans%=mod;
        }
    }
    if(A>1){
        ll MOD=mod*(A-1);
        ans*=(fpow(A,B+1,MOD)+MOD-1)/(A-1);
        ans%=mod;
    }
    printf(LL"\n",ans);
}
int main(){
    get_prime();
    for(ll A,B;scanf(LL LL,&A,&B)==2;) factor(A,B);
    return 0;
}