Description：

给出 $N$ 和 $G$ ，求 $G^{\begin{align}\sum_{d|N}C_N^d\end{align}}mod\ 999911659$

$N,G \le 10^9$

Solution：

由欧拉定理得 $G^{\begin{align}\sum_{d|N}C_N^d\end{align}}mod\ 999911659$ $=$ $ G^{\begin{align}\sum_{d|N}C_N^d\end{align}mod\ 999911658}mod\ 999911659$

$999911658=2\times3\times 4679\times 35617$

用（假的）扩展卢卡斯定理分别求出对于每个素因数模完的结果最后再用中国剩余定理合并，由于每个素因数都是一次方，所以可以直接上卢卡斯定理，预处理阶乘及阶乘逆元，注意处理阶乘逆元时倒推。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll n,g,prime[5] = {0,2,3,4679,35617};

#define MOD 999911659

#define PHI 999911658

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

#define MAXN 40010

ll fac[MAXN],inv[MAXN];

ll C(ll n,ll m,ll mod)

{

	if(n < m)return 0;

	if(n < mod && m < mod)return fac[n] * inv[m] % mod * inv[n - m] % mod;

	return C(n % mod,m % mod,mod) * C(n / mod,m / mod,mod) % mod;

}

ll get(ll k)

{

	fac[0] = 1;

	for(int i = 1;i < k;++i)fac[i] = fac[i - 1] * i % k;

	inv[k - 1] = k - 1;

	for(int i = k - 2;i >= 0;--i)inv[i] = inv[i + 1] * (i + 1) % k;

	ll ans = 0;

	for(int i = 1;i <= sqrt(n);++i)

	{

		if(n % i == 0)

		{

			ans = (ans + C(n,i,k)) % k;

			if(n / i != i)

			{

				ans = (ans + C(n,n / i,k)) % k;

			}

		}

	}

	return ans;

}

ll a[5];

ll exgcd(ll a,ll b,ll &x,ll &y)

{

	if(b == 0)

	{

		x = 1;y = 0;

		return a;

	}

	ll k = exgcd(b,a % b,x,y);

	ll t = x;

	x = y;

	y = t - a / b * y;

	return k;

}

ll que(ll k,ll mod)

{

	ll x,y;

	exgcd(k,mod,x,y);

	while(x < 0)x += mod;

	return x;

}

ll CRT()

{

	for(int i = 1;i <= 4;++i)

	{

		a[i] = get(prime[i]);

	}

	ll ans = 0;

	for(int i = 1;i <= 4;++i)

	{

		ans = (ans + (a[i] * (PHI / prime[i]) % PHI * que(PHI / prime[i],prime[i])) % PHI) % PHI;

	}

	return ans;

}

int main()

{

	scanf("%lld%lld",&n,&g);

	if(g % MOD == 0)

	{

		puts("0");

		return 0;

	}

	printf("%lld\n",power(g,CRT()));

	return 0;

}