#include <iostream>
#include <cmath>
using namespace std;
long long a,b,r,f[114514];
struct yinzi{
	long long zhi;
	long long num;
}c[114514];
void fenjie(long long p){
	for(int i=2;i<=p;i++){
		if(p%i==0){
		//	cout<<i<<endl;
			p/=i;
			if(c[r].num==i)
				c[r].zhi++;
			else
				c[++r].num=i,c[r].zhi=1;
			i--;
		}
	}
	for(int i=1;i<=r;i++)
		c[i].zhi*=b;
}
long long mi(long long di,long long zhi){
	long long ans=1;
	while(zhi){
		if(zhi%2)
			ans=ans*di%9901;
		zhi/=2;
		di=di*di%9901;
	}
	return ans%9901;
}
long long dengbi(long long bizhi,long long xiangshu){
	if(xiangshu==0)
		return 0;
	if(xiangshu%2)
		return ((1+mi(bizhi,xiangshu/2))*dengbi(bizhi,xiangshu/2)+mi(bizhi,xiangshu-1))%9901;
	return (1+mi(bizhi,xiangshu/2))*dengbi(bizhi,xiangshu/2)%9901;
}
long long qiu(int shu){
	if(shu>r)
		return 1;
	if(f[shu])
		return f[shu];
	return f[shu]=(dengbi(c[shu].num,c[shu].zhi+1)*qiu(shu+1))%9901;
}
int main(){
	cin>>a>>b;
	fenjie(a);
	if(a==0)
		cout<<0;
	else
		cout<<(qiu(1)+9901)%9901;
}