#include<fstream>
using namespace std;
ifstream cin("sumdiv.in");
ofstream cout("sumdiv.out");
const int N=9901;
int A(int a,int n)
{
int b=1;
for(;n;a=a*a%N,n>>=1)
if(n&1)
b=a*b%N;
return b;
}
int main()
{
int a,b;
if(cin>>a>>b,!b||a<2)
return cout<<-1,0;
int c=b%(N-1),d=1;
if(cin>>a>>b,c=b%(N-1),!(a&1)) {
int p=1;
for(a>>=1;!(a&1);a>>=1,++p);
if(d=A(2,(c*p+1)%(N-1))-1,d<0)
d+=N;
}
for(int i=3;i*i<=a;i+=2)
if(a%i<1) {
int p=1,q;
for(a/=i;a%i<1;a/=i,++p);
if(q=A(i,(c*p+1)%(N-1))-1,q<0)
q+=N;
d=d*q%N*A(i-1,N-2)%N;
}
if(a>1) {
int p=a%N;
if(p!=1) {
int q=A(p,c+1)-1;
if(q<0)
q+=N;
d=d*q%N*A(p?p-1:N-1,N-2)%N;
} else
d=d*(b%N+1)%N;
}
return cout<<d,0;
}