如题

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e7+10,mod=9901;
ll m,n,num[N],sum=1;
bool su[N];
queue<ll> q;
struct matrix{
	ll m[2][2];
};
matrix operator * (const matrix &a,const matrix &b){
	matrix c;
	memset(c.m,0,sizeof(c.m));
	for(int i=0;i<2;++i)
	for(int j=0;j<2;++j)
	for(int k=0;k<2;++k)
	c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
	return c;
}
ll ksm(ll s,ll t){
	matrix ans,a;
	a.m[0][0]=s,a.m[1][0]=s,a.m[1][1]=1,a.m[0][1]=0;
	ans.m[0][0]=1,ans.m[0][1]=0,ans.m[1][1]=1,ans.m[1][0]=0;
	while(t>0){
		if(t&1) ans=ans*a;
		a=a*a;
		t>>=1;
	}
	return ans.m[1][0];
}
void _init(){
	su[1]=true;
	for(int i=2;i<=sqrt(m);++i)
	if(!su[i])
	for(int j=2;j<=sqrt(m);++j)
		su[i*j]=true;
	ll i=1;
	while(m^1){
		while(su[i]) ++i;
		if(!(m%i)){
			if(!num[i]) q.push(i);
			++num[i];
			m/=i;
		}
		else ++i;
	}
}
int main(){
	matrix b;
	scanf("%ld%ld",&m,&n);
	_init();
	while(!q.empty()){
		ll i=q.front();
		q.pop();
		sum*=(ksm(i,n*num[i])+1);
		sum%=mod;
	}
	printf("%ld",sum);
	return 0;
}