#14蒟蒻求助

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int a=1,b=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while('0'<=ch&&ch<='9') b=b*10+ch-'0',ch=getchar();
    return b;
}
const int p=9901;
int s[65],cnt,ss[65],ct,ans=1;
int qpow(int a,int b){
    int anss=1;
    while(b){
        if(b&1) anss=anss*a%p;
        a=a*a%p;
        b>>=1;
    }
    return anss%p;
}
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;y=0;return a;
    }
    int r=exgcd(b,a%b,x,y);
    int tem=x;
    x=y;
    y=tem-a/b*y;
    return r;//
}
int niyuan_tongyu(int a){
    int x,y;
    int d=exgcd(a,p,x,y);
    //if(d!=1) return -1;//无解
    return (x%p+p)%p;
}
int calc(int a,int b){
    if(a%p==1) return b+1;
    else {
        //printf("%lld\n",pow(a,b+1)-1);
        return ((qpow(a,b+1)-1)%p*niyuan_tongyu(a-1)%p)%p;
    }
}
signed main()
{
    int a,b,k=1;
    a=read();b=read();
    //if(a==0) {cout<<0<<endl;return 0;}//特判 
    //if(b==0||a==1) {cout<<1<<endl;return 0;}
    for(int i=2;i<=a-1;i++){
        if(a/i==a*1.0/i) {s[++cnt]=i,ss[cnt]=1;
        k=a/i;
        while(k){
        if(k/i==k*1.0/i) ss[cnt]++,k/=i;
        else break;}
        a=k;
        }
    }
    if(a!=1) {s[++cnt]=a;ss[cnt]=1;}
    //printf("%lld %lld\n",s[i],ss[i]);
    for(int i=1;i<=cnt;i++){
        ss[i]*=b;
    }
    for(int i=1;i<=cnt;i++){
        ans=(ans%p*calc(s[i],ss[i])%p)%p;
    }
    printf("%lld",ans%p);
    return 0;
}