记录编号	364117	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]艾米利亚的魔法	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	5.773 s
提交时间	2017-01-15 14:46:31	内存使用	7.92 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+10,mod=54184622,phi=mod/2-1;
const int p[5]={2,3,5,7,129011};
int n,g,a[5];ll x,y,ans,now,inv[N];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void ex_gcd(ll a,ll b,ll &x,ll &y){
	if (!b){x=1;y=0;return;}
	ex_gcd(b,a%b,x,y);
	ll m=x;
	x=y;y=m-a/b*y;
}
void mul(int x){
	for (int i=0;i<5;i++)
		while (!(x%p[i])) a[i]++,x/=p[i];
	now=now*x%phi;
}
void del(int x){
	for (int i=0;i<5;i++)
		while (!(x%p[i])) a[i]--,x/=p[i];
	now=now*inv[x]%phi;
}
ll mi(ll x,ll y,ll mod){
	ll ans=1;
	for (;y;y>>=1,x=x*x%mod)
		if (y&1) ans=ans*x%mod;
	return ans;
}
ll k(){
	ll ans=now;
	for (int i=0;i<5;i++) ans=ans*mi(p[i],a[i],phi)%phi;
	return ans;
}
int main()
{
	freopen("aimiliyademagic.in","r",stdin);
	freopen("aimiliyademagic.out","w",stdout);
	scanf("%d%d",&n,&g);
	for (int i=1;i<=1e6;i++)
	if (gcd(i,phi)==1){
		ex_gcd(i,phi,x,y);
		inv[i]=(x%phi+phi)%phi;
	}
	ans=now=1;
	for (int i=1;i<=n&&i<=g;i++){
		mul(g-i+1);del(i);
		if (gcd(i,n)==1){
			ll K=k()+phi;
			ans=ans*mi(n,K,mod)%mod;
		}
	}
	printf("%lld\n",ans);
	return 0;
}