1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <cstdio>
typedef long long int ll;
const int mod=999911658;
const int pri[4]={2,3,4679,35617};
inline int qpow(int n,int k,int p) {
int ans=1;
while(k) {
if(k&1) ans=(ll)ans*n%p;
n=(ll)n*n%p;k>>=1;
}
return ans;
}
int pre[40005][4],inv[40005][4];
inline void exgcd(int a,int b,int &x,int &y) {
if(!b) {x=1;y=0;}
else {exgcd(b,a%b,y,x);y-=a/b*x;}
}
int Lucas(int n,int k,int id) {
if(k>n) return 0;
else if(!k||n==k) return 1;
else if(n<pri[id]&&k<pri[id]) return (ll)pre[n][id]*inv[n-k][id]%pri[id]*inv[k][id]%pri[id];
return (ll)Lucas(n/pri[id],k/pri[id],id)*Lucas(n%pri[id],k%pri[id],id)%pri[id];
}
int n,g;
inline int ExLucas(int k) {
int ans=0;
for(register int j=0;j<4;++j) {
int x,y;exgcd(mod/pri[j],pri[j],x,y);x=(x%pri[j]+pri[j])%pri[j];
ans=(ans+(ll)Lucas(n,k,j)*x%mod*(mod/pri[j])%mod)%mod;
}
return ans;
}
int main() {
scanf("%d%d",&n,&g);
if(g==999911659) {puts("0");return 0;}
for(register int j=0;j<4;++j) pre[0][j]=inv[0][j]=1;
for(register int i=1;i<=35617;++i) {
for(register int j=0;j<4;++j) {
pre[i][j]=(ll)pre[i-1][j]*i%pri[j];
inv[i][j]=qpow(pre[i][j],pri[j]-2,pri[j]);
}
}
int ans=0;
for(register int i=1;i*i<=n;++i) if(n%i==0) {
ans=(ans+ExLucas(i))%mod;
if(i*i!=n) ans=(ans+ExLucas(n/i))%mod;
}
printf("%d\n",qpow(g,ans,999911659));
return 0;
}
|