#include <iostream>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
using namespace std;

ifstream f("sumdiv.in");
ofstream g("sumdiv.out");

const long long int MOD=9901;
long long n,p,jkl=0,t,actual;
long long prod=1;

int invers(int nr,int ad,int x)
 {
  if(nr!=MOD-2)
   {
   if(nr+ad<=MOD-2)
    {
     t=(1LL*t*x)%MOD;
     x=(1LL*x*x)%MOD;
     nr+=ad;
     ad*=2;
     invers(nr,ad,x);
    }
   else invers(nr,1,actual);
   }
 }

 int exp(int nr,int ad,int x)
  {
   if(nr!=jkl)
   {
   if(nr+ad<=jkl)
    {
     t=(1LL*t*x)%MOD;
     x=(1LL*x*x)%MOD;
     nr+=ad;
     ad*=2;
     exp(nr,ad,x);
    }
   else exp(nr,1,actual);
   }
  }

int main()
{
f>>n>>p;
for(int i=2;i*i<=n;i++)
 {
  if(n%i==0)
   {
    jkl=0;
    while(n%i==0)
    {n/=i; jkl++;}
    jkl*=p;
    jkl++;
    actual=i-1;
    t=actual;
    invers(1,1,t);
    prod=(1LL*prod*t)%MOD;
    actual=i;
    t=actual;
    exp(1,1,t);
    t--;
    prod=(1LL*prod*t)%MOD;
   }
 }
if(n!=1)
 {
  jkl=1;
  actual=n-1;
  jkl*=p;
  jkl++;
  t=actual;
  invers(1,1,t);
  prod=(1LL*prod*t)%MOD;
  actual=n;
  t=actual;
  exp(1,1,t);
  t--;
  prod=(1LL*prod*t)%MOD;
 }
g<<prod;
}