代码1（非标准，快）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL fac[50000],a[5],b[5]={0,2,3,4679,35617}; 
LL qpow(LL a,LL b,LL p)  
{
	LL ans=1%p;a%=p;
	for(;b;b>>=1)
	{
		if(b&1)ans=ans*a%p;
		a=a*a%p;
	}
	return ans;
}  
LL C(LL n,LL m,LL p)  
{
	if(n<m)return 0;
	return fac[n]*qpow(fac[m],p-2,p)%p*qpow(fac[n-m],p-2,p)%p;  
}  
LL Lucas(LL n,LL m,LL p)  
{
	if(m==0)return 1;
	return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;  
}  
int main()
{
	LL n,q;cin>>n>>q;
	LL P=999911658;
	if(q % (P+1) ==0) {printf("0\n");return 0;}
	memset(a,0,sizeof(a));
	for(int i=1;i<=4;i++)
	{
		int p=b[i];
		fac[0]=1;for(int j=1;j<=p;j++)fac[j]=fac[j-1]*j%p;
		for(int d=1;d*d<=n;d++)if(n%d==0)
		{
			a[i]=(a[i]+Lucas(n,d,p))%p;
			if(d*d!=n)a[i]=(a[i]+Lucas(n,n/d,p))%p;
		}
	}
	//中国剩余定理CRT 
	LL x=0;
	for(int i=1;i<=4;i++)
	{
		LL p=b[i];
		LL z=P/b[i];//z为砖 ,z % b[i] 不一定等于1 
		LL dz= z * qpow(z,p-2,p)%P;//dz为大砖 ，保证 dz % b[i]==1 
		x+= a[i]*dz %P;
		x%=P;
	}
	LL ans=qpow(q,x,P+1);
	cout<<ans<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
LL a[N], b[N], c[N]; int cnt;
LL qpow(LL a, LL b, LL P)
{
    LL ans=1%P; a%=P;
    for(; b; b>>=1)
    {
        if(b&1) ans=ans*a%P;
        a=a*a%P;
    }
    return ans;
}
void exgcd(LL a, LL b, LL &d, LL &x, LL &y)
{
    if(b==0) {d=a; x=1; y=0;}
    else
    {
        exgcd(b, a%b, d, y, x);
        y-=(a/b)*x;
    }
}
LL inv(LL a, LL P)
{
    LL A=a, B=P, K=1, d, x, y;
    exgcd(A, B, d, x, y);
    x=x*(K/d); LL dx=abs(B/d); x=(x%dx+dx)%dx;
    return x;
}
LL fac(LL n, LL P, LL Pk)
{
    LL ans=1; if(n==0) return 1;
    for(LL i=1; i<Pk; i++) if(i%P!=0) ans=(ans*i)%Pk;
    ans=qpow(ans, n/Pk, Pk);
    for(LL i=1; i<=n%Pk; i++) if(i%P!=0) ans=(ans*i)%Pk;
    return ans*fac(n/P, P, Pk)%Pk;
}
LL C(LL n, LL m, LL P, LL Pk)
{
    if(n<m) return 0;
    LL f1=fac(n, P, Pk), f2=fac(m, P, Pk), f3=fac(n-m, P, Pk), sum=0;
    for(LL i=n; i; i/=P) sum+=i/P;
    for(LL i=m; i; i/=P) sum-=i/P;
    for(LL i=n-m; i; i/=P) sum-=i/P;
    return f1*inv(f2, Pk)%Pk*inv(f3, Pk)%Pk*qpow(P, sum, Pk)%Pk;
}
LL CRT()
{
    LL m=1, ans=0;
    for(int i=1; i<=cnt; i++) m*=c[i];
    for(int i=1; i<=cnt; i++)
    {
        ans=(ans+a[i]*(m/c[i])%m*inv(m/c[i], c[i])%m)%m;
    }
    return ans;
}
LL exLucas(LL n, LL m, LL P)
{
    for(int i=1; i<=cnt; i++) a[i]=C(n, m, b[i], c[i]);
    return CRT();
}
int main()
{
    LL n, q; scanf("%lld%lld", &n, &q);
    LL P=999911658,x=0;
cnt=0;LL p=P; 
for(int i=2; i*i&lt;=p; i++) if(p%i==0)
{
    b[++cnt]=i;c[cnt]=1;while(p%i==0) {c[cnt]*=i; p/=i;}
}
if(p&gt;1) {b[++cnt]=p;c[cnt]=p;}
 
for(int d=1;d*d&lt;=n;d++)if(n%d==0)
{
    x+=exLucas(n&#44; d&#44; P);
    if(d*d!=n)x+=exLucas(n&#44; n/d&#44; P);
    x%=P;
}
if(q==P+1) printf("0\n");else printf("%lld\n"&#44;qpow(q&#44;x&#44;P+1) );
return 0;

}