记录编号	456799	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]艾米利亚的魔法	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	16.965 s
提交时间	2017-10-05 16:44:55	内存使用	91.87 MiB

#pragma GCC optimize("O3")
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 200005
#define mod 54184622
#define M 27092310
#define ll long long
using namespace std;
int read()
{
	int sum=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}
	return sum*f;
}
ll n,g,a[6],b[6],pri[6]={2,3,5,7,129011},ans;
ll s1[6][1000005],s2[6][1000005];
ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}
ll cheng(ll x,ll n,ll p)
{
	ll ans=1;
	while(n)
	{
		if(n&1)ans=ans*x%p;
		x=x*x%p;
		n/=2;
	}
	return ans;
}
ll get(ll n,ll m,ll p,int i)
{
	if(m>n)return 0;
	return ((s1[i][n]*s2[i][m]%p)*s2[i][n-m])%p;
}
ll lucas(ll n,ll m,ll p,int i)
{
	if(m==0)return 1;
	return get(n%p,m%p,p,i)*lucas(n/p,m/p,p,i)%p;
}
ll C(ll n,ll m)
{
	if(m>n)return 0;
	ll sum=0;
	for(int i=0;i<5;i++)
	{
		ll k=lucas(n,m,pri[i],i);
		sum=(sum+k*a[i]*b[i]%M)%M;
	}
	return sum;
}
void init()
{
	for(int i=0;i<5;i++)
	{
		s1[i][0]=1;
		for(ll j=1;j<=1000000;j++)s1[i][j]=(s1[i][j-1]*j)%pri[i];
		for(ll j=0;j<=1000000;j++)s2[i][j]=cheng(s1[i][j],pri[i]-2,pri[i]);
		a[i]=M/pri[i];
		b[i]=cheng(a[i],pri[i]-2,pri[i]);
	}
}
int main()
{
	freopen("aimiliyademagic.in","r",stdin);
	freopen("aimiliyademagic.out","w",stdout);
	n=read();g=read();
	init();
	for(ll i=1;i<=n;i++)
	{
		ll k=gcd(i,n);
		if(k!=1)continue;
		ans+=C(g,i);
		ans%=M;
	}
	printf("%lld\n",cheng(n,ans+M,mod));
}