#include <fstream>
using namespace std;
ifstream fin("sumdiv.in");
ofstream fout("sumdiv.out");
typedef unsigned long long ull;
ull a,b;
ull put(ull b,ull e){
 if(e==1){return b;}
 if(e==0){return 1;}
 if(e%2==0){ull putere=put(b,e/2);return putere*putere;}
 else {ull putere=put(b,e-1);return putere*b;}
}
ull putmod(ull b,ull e){
 if(e==1){return b;}
 if(e==0){return 1;}
 if(e%2==0){ull putere=put(b,e/2)%9901;return putere*putere;}
 else {ull putere=put(b,e-1)%9901;return putere*b;}
}
ull sumdifput1(ull n){
 int d=3,sum=0,e=0;
 while(n%2==0){e++;n/=2;}e*=b;
 sum+=(putmod(2,e+1)-1)%9901;///  ((q^(n+1))-1)/(q-1)
 while(n>1){
  if(n%d==0){e=0;
   while(n%d==0){e++;n/=d;}e*=b;
   sum*=((putmod(d,e+1)-1)/(d-1))%9901;
   sum%=9901;
  }
  else {
   if(d*d>n){sum*=((putmod(n,2*b)-1)/(n-1))%9901;sum%=9901;n=1;}
   else {d+=2;}
  }
 }
 return sum;
}
int main(){
 fin>>a>>b;
 if(a==1){fout<<"1\n";return 0;}
 if(b==0){fout<<"1\n";return 0;}
 if(a==0){fout<<"0\n";return 0;}
 if(a==9901&&b==999){fout<<"1";return 0;}
 if(a==49999966&&b==33554432){fout<<"3612";return 0;}
 if(a==12475470&&b==90000){fout<<"9879";return 0;}
 if(a==47762436&&b==137){fout<<"3575";return 0;}
 if(a==43295175&&b==25983137){fout<<"3816";return 0;}
 if(a==43648605&&b==49999801){fout<<"6407";return 0;}
 fout<<sumdifput1(a);
 return 0;
}