#include <fstream>
#include <bitset>
#define mod 9901
using namespace std;
ifstream fin("sumdiv.in");
ofstream fout("sumdiv.out");
long long t,i,f[1000010],v[1000010],k,j,b;
long long sumel,n;
long long RID(long long n,long long exp)
{
    long long sol=1;
    while(exp>0)
    {
        if(exp%2==1) sol=(1ll*sol*n)%mod;
        n=(n*n)%mod;
        exp/=2;
    }
    return sol;
}

void dez(long long d)
{
    long long nr=0;
    while(n%d==0) n/=d,nr++;
    if(nr==0) return;
    nr*=b;
    long long val=RID(d%mod,nr+1)-1;
    if(val<0) val+=mod;
    sumel*=val*RID((d-1)%mod,mod-2);
    sumel%=mod;
    if(sumel<0) sumel+=mod;
}
int main()
{
    for(i=3;i*i<=100000;i+=2)
        if(f[i]==0) for(j=i*3;j<=100000;j+=i*2) f[j]=1;
    v[++k]=2;
    for(i=3;i<=1000000;i+=2) if(f[i]==0) v[++k]=i;
    fin>>n>>b;sumel=1;
    for(i=1;i<=k&&v[i]*v[i]<=n;i++) if(n%v[i]==0) dez(v[i]);
    if(n!=1) dez(n);
    fout<<sumel<<"\n";
    return 0;
}