#include <iostream>
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll maxn=50000005;
ll factor[100];
ll num[maxn];
ll cnt;
void getfactor(ll A,ll B){
    cnt=0;
    for(ll i=2;i*i<=A;i++){
        int count=0;
        if(A%i!=0)continue;
        while(A%i==0){
            A/=i;
            count++;
        }
        num[cnt]=count*B;
        factor[cnt++]=i;
    }
    if(A!=1){
        num[cnt]=B;
        factor[cnt++]=A;
    }
}
ll multiply(ll a,ll b,ll mod){
    ll res=0;
    while(b){
        if(b&1){
            res+=a;
            if(res>=mod)res-=mod;
        }
        a<<=1;
        b>>=1;
        if(a>=mod)a-=mod;
    }
    return res;
}
ll exp_mod(ll a, ll b,ll c){
    ll res=1;
    while(b){
        if(b&1)res=multiply(res,a,c);
        b>>=1;
        a=multiply(a,a,c);
    }
    return res;
}
ll solve(ll p,ll n){
    return (exp_mod(p,n+1,(p-1)*9901)-1)/(p-1);
}
int main()
{
    ll A,B;
    while(scanf("%I64d%I64d",&A,&B)!=EOF){
        getfactor(A,B);
        ll res=1;
        for(ll i=0;i<cnt;i++){
            res=multiply(res,solve(factor[i],num[i]),9901);
        }
        printf("%I64d\n",res);
    }
    return 0;
}