#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=9901;
int a,b,ans=1;
int qpow(int j,int p){
	int sum=1;
    while(p>0){
        if(p%2!=0) sum=sum*j%mod;
        j=j*j%mod;
        p=p>>1;
    }
    return sum;
}
int ppp(int x,int y){
	if(x==0) return 1;
	else if(x%2==1) return ppp(x/2,y)*(1+qpow(y,x/2+1))%mod;
	else return (ppp(x/2-1,y)*(1+qpow(y,x/2+1))+qpow(y,x/2))%mod;

}
signed main() {
	cin>>a>>b;
	for(int i=2;i*i<=a;i++){
	    if(a%i==0){
	        int s=0;
	        while(a%i==0) s++,a/=i;
	        ans=(ans*ppp(s*b,i))%mod;
	    }
	}
 	if(a!=0) ans=(ans*ppp(b,a))%mod;
	cout<<ans%9901;

	return 0;
}

WA on 15