记录编号	550771	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SDOI 2010] 古代猪文	最终得分	100
用户昵称	斯内普和骑士	是否通过	通过
代码语言	C++	运行时间	0.077 s
提交时间	2020-03-16 22:53:39	内存使用	14.04 MiB

#include<bits/stdc++.h>
using namespace std;
#define R register
typedef long long ll;
const int MOD=999911658;
const int maxn=50010;
ll fac[maxn],a[5],b[5]={0,2,3,4679,35617};
ll n,G,g_h_y;
inline ll qpow(ll g,ll k,ll mod)
{
	ll res=1;
	while(k)
	{
		if(k&1)
		res=(res*g)%mod;
		if(k>>=1)
		g=g*g%mod;
	}
	return res;
}
inline void init(ll mod)
{
	fac[0]=1;
	for(R ll i=1;i<=mod;i++)
	fac[i]=fac[i-1]*i%mod;
}
inline ll C(ll n,ll m,ll mod)
{
	if(m>n)
	return 0;
	return fac[n]*qpow(fac[m],mod-2,mod)%mod*qpow(fac[n-m],mod-2,mod)%mod;
}
inline ll Lucas(ll n,ll m,ll mod)
{
	if(n<m)
	return 0;
	if(!n)
	return 1;
	return Lucas(n/mod,m/mod,mod)*C(n%mod,m%mod,mod)%mod;
}
void CRT()
{
	for(R ll i=1;i<=4;i++)
	g_h_y=(g_h_y+a[i]*(MOD/b[i])%MOD*qpow(MOD/b[i],b[i]-2,b[i]))%MOD;
}
int main()
{
	 freopen("pigpassage.in","r",stdin);
	 freopen("pigpassage.out","w",stdout);
	 scanf("%lld%lld",&n,&G);
	 if(G%(MOD+1)==0)
	 {
	 	printf("0\n");
	 	return 0;
	 }
	 for(R ll i=1;i<=4;i++)
	 {
	 	init(b[i]);
	 	for(R ll j=1;j*j<=n;j++)
	 	{
	 		if(n%j==0)
	 		{
	 			a[i]=(a[i]+Lucas(n,j,b[i]))%b[i];
	 			if(j*j!=n)
	 			{
	 				a[i]=(a[i]+Lucas(n,n/j,b[i]))%b[i];
	 			}
	 		}
	 	}
	 }
	 CRT();
	 ll ans=qpow(G,g_h_y,MOD+1);
	 printf("%lld\n",ans);
	 return 0;
}