看到取余就想到逆元,所以就有了如下代码......
#include<bits/stdc++.h>
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
const int INF = 0x3f3f3f3f, nINF = 0xcfcfcfcf, INFMEM = 0x3f, nINFMEM = 0xcf;
const int PR1 = 1e6 + 3, PR2 = 1e9 + 7;
using namespace std;
#define rd(x) scanf("%d",&x)
#define lrd(x) scanf("%lld",&x)
#define pt(x) printf("%d\n",(x))
typedef long long ll;
typedef double db;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int N = 5e7, mod=9901;
int a,b;
int pri[N],e[N],tot;
ll ans=1;
bool is_prime(int x){
if(x==1) return false;
if(x==2||x==3) return true;
if(x%2==0||x%3==0) return false;
for(int i = 5; i*i <= x; i+=6) if(x%i==0 || x%(i+2)==0) return false;
return true;
}
void divi(int x){
for(int i = 2; i <= x; i++){
if(!is_prime(i)) continue;
if(x%i==0) pri[++tot]=i;
while(x%i==0) e[tot]++, x/=i;
}
}
ll qpow(ll n, ll k){
ll ret=1;
while(k){
if(k&1) ret=ret*n%mod;
n=n*n%mod; k>>=1;
}
return ret;
}
int main(){
rd(a); rd(b);
if(a==0) {
printf("0\n");
return 0;
}
divi(a);
//rep(i,1,tot) printf("%d^%d ",pri[i],e[i]);
rep(i,1,tot) {
ans=ans*(qpow(pri[i],e[i]*b+1)-1)%mod*qpow(pri[i]-1,mod-2)%mod;
}
printf("%lld\n",(ans%mod+mod)%mod);
return 0;
}