#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int mod=9901;
const int N=7100;
#define ll long long
int prime[N+1];
void get_prime(){
    for(int i=2;i<=N;i++){
        if(!prime[i])prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&i*prime[j]<=N;j++){
            prime[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int factor[100][2],fatCnt;
void get_factor(ll x){
    memset(factor,0,sizeof factor),fatCnt=0;
    for(int i=1;i<=prime[0];i++){
        if(x%prime[i]==0){
            factor[fatCnt][0]=prime[i];
            while(x%prime[i]==0)x/=prime[i],factor[fatCnt][1]++;
            fatCnt++;
        }
    }
    if(x!=1)factor[fatCnt][0]=x,factor[fatCnt++][1]=1;
}
ll Pow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll sum(ll p,ll n){
    if(p==0)return 0;
    if(n==0)return 1;
    if(n&1) return ((1+Pow(p,n/2+1))%mod*sum(p,n/2)%mod)%mod;
    else return ((1+Pow(p,n/2+1))%mod*sum(p,n/2-1)+Pow(p,n/2)%mod)%mod;
}
ll slove(ll A,ll B){
    get_factor(A);
    ll ans=1;
    for(int i=0;i<fatCnt;i++){
        ans*=sum(factor[i][0],B*factor[i][1])%mod;
        ans%=mod;
    }
    return ans;
}
int main(){
    get_prime();
    ll A,B;
    while(cin>>A>>B) cout<<slove(A,B)<<endl;
}