求 \(A^B\) 的约数和模 MOD
对 A 质因子分解 P1^k1*P2^k2….P^kn
A^B 即指数对应部分乘以 B
对于每个 P 都有 (1+P^1+P^2+…+P^ki) 的选择
连乘每一个 P 的等比数列之和即可
这里用了分治法，我觉得有必要记一下，不然推错就麻烦了
奇数部分 sum(p,c)=(1+p^(c+1»1))sum(p,c-1»1)
偶数部分 sum(p,c)=(1+p^(c»1))sum(p,c/2-1)+p^c
/*H E A D*/
inline int mod(ll a){
return a%MOD;
}
int fpw(ll a,ll n){
ll ans=1;
while(n){
if(n&1) ans=mod(ans*a);
a=mod(a*a);
n>>=1;
}
return mod(ans);
}
int sum(int p,int n){
if(n==0)return 1;
if(n&1) return mod(mod(1+fpw(p,n+1>>1))*mod(sum(p,n-1>>1)));
else return mod(mod(1+fpw(p,n>>1))*mod(sum(p,(n>>1)-1))+mod(fpw(p,n)));
}
ll n,cnt;
ll prime[maxn],num[maxn];
void chai(ll a){
cnt=0;
memset(num,0,sizeof num);
memset(prime,0,sizeof prime);
for(ll i = 2; i*i <= a; i++){
if(a%i==0){
cnt++;
prime[cnt]=i;num[cnt]++;
a/=i;
while(a%i==0){
num[cnt]++;
a/=i;
}
}
}
if(a>1){
cnt++;
prime[cnt]=a;
num[cnt]=1;
}
}
int main(){
ll a,b;
while(~lin(a)){
b=read();
chai(a);
rep(i,1,cnt) num[i]*=b;
// rep(i,1,cnt) cout<<i<<" "<<prime[i]<<" "<<num[i]<<endl;
ll ans=1;
rep(i,1,cnt){
int tmp=sum(prime[i],num[i]);
ans=mod(ans*mod(tmp));
}
println(ans);
}
return 0;
}