#include <stdio.h>
#include <math.h>

using namespace std;
FILE *f=fopen("sumdiv.in","r");
FILE *g=fopen("sumdiv.out","w");

const int mod=9901;

short cr[10001];
int a,b,i,sum,p,max;

unsigned long long ridic(long long n,long long k)
{
 unsigned long long i,a,s;
 a=n;
 s=1;
 for(i=0;(1<<i)<=k;i++)

  {
    if (((1<<i)&k)>0)s=(s*a)%mod;
   a=(a*a)%mod;
  }
return s;
}

void ciur()
{
 int i,j;

 for(i=3;i<=max;i+=2)
   if (cr[i]==0)
     for(j=i+i;j<=max;j+=i)
      cr[j]=1;
}


int main()
{
fscanf(f,"%d%d",&a,&b);
b=b%(mod-1);
max=trunc(sqrt(a));
sum=0;
ciur();
for(i=2;i*i<=a;i++)
if (cr[i]==0 && a%i==0)
{
    p=0;
    while(a%i==0){a=a/i;p++;}

sum=(sum+((ridic(i,(p*b+1))-1)%mod)/(i-1))%mod;
}
if (a!=1)
{
sum=(sum+((ridic(a,b+1)-1)%mod)/(a-1))%mod;
}

fprintf(g,"%d",sum);
fclose(g);
return 0;
}