#include <cstdio>
#define NMax 10

const int MOD = 9901;
int f[NMax+1];
int g[NMax+1];

int LgPut(int X, int B)
{
    int A = 1;
    while(B)
    {
        if(B%2) A=(A*X)%MOD;
        X=(X*X)%MOD;
        B/=2;
    }
    return A;
}

int main(){
    FILE* fin = fopen("sumdiv.in","r");
    FILE* fout = fopen("sumdiv.out","w");

    int i,A,B,res,inv,nr=0;

    fscanf(fin,"%d %d",&A,&B);
    for(i = 2; i * i <= A; ++i)
    if(A % i == 0){
        ++nr;
        f[nr] = i;
        while(A % i == 0) { A /= i; ++g[nr]; }
    }

    if(A > 1) { f[++nr] = A; g[nr] = 1; }
    for(i = 1; i <= nr; ++i) g[i] = g[i] * B;

    res = inv = 1;
    for(i = 1; i <= nr; ++i) inv = (inv * LgPut(f[i]-1,MOD-2)) % MOD;
    for(i = 1; i <= nr; ++i) res = (res * (LgPut(f[i],g[i]+1)+MOD-1)) % MOD;
    fprintf(fout,"%d\n",(res*inv)%MOD);

    fclose(fin);
    fclose(fout);


return 0;
}