记录编号	456207	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]艾米利亚的魔法	最终得分	100
用户昵称	xyz117	是否通过	通过
代码语言	C++	运行时间	10.941 s
提交时间	2017-10-04 11:07:26	内存使用	12.13 MiB

#pragma GCC optimize("O3")
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define mod 54184622
#define MOD 27092310
#define LL long long
template<typename __>
inline void read(__ &s)
{
    s=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        s=s*10+ch-'0',ch=getchar();
}
int N,G;
namespace solveB
{
    #define maxn 129020
    LL fac[6][maxn],inv[6][maxn];
    LL module[6]={27092310,2,3,5,7,129011};
    inline LL qpow(LL x,LL y,LL modu)
    {
        LL ans=1;
        for(;y;y>>=1,x=x*x%modu)
            if(y&1)
                ans=ans*x%modu;
        return ans;
    }
    void init(int x,int cnt)
    {
        fac[cnt][0]=fac[cnt][1]=1;
        for(int i=2;i<x;i++)
            fac[cnt][i]=fac[cnt][i-1]*i%x;
        inv[cnt][0]=inv[cnt][1]=1;
        for(int i=2;i<x;i++)
            inv[cnt][i]=(x-x/i)*inv[cnt][x%i]%x;
        for(int i=1;i<x;i++)
            inv[cnt][i]=inv[cnt][i-1]*inv[cnt][i]%x;
    }
    inline LL C(LL n,LL m,int cnt)
    {
        if(n<m)
            return 0;
        return (fac[cnt][n]*inv[cnt][m]%module[cnt]*inv[cnt][n-m])%module[cnt];
    }
    inline LL lucas(int n,int m,int cnt)
    {
        if(n<m)
            return 0;
        LL ans=1;
        LL p1=module[0],p2=module[cnt];
        for(;m;m/=module[cnt],n/=module[cnt])
            ans=ans*C(n%p2,m%p2,cnt)%p2;
        return ans*(p1/p2)%p1*qpow(p1/p2,p2-2,p2)%p1;
    }
    inline LL combin(int n,int m)
    {
        LL ans=0;
        for(int i=1;i<=5;i++)
            ans=(ans+lucas(n,m,i))%module[0];
        return ans;
    }
    void solve()
    {
        for(int i=1;i<=5;i++)
            init(module[i],i);
    }
}
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    freopen("aimiliyademagic.in","r",stdin);
    freopen("aimiliyademagic.out","w",stdout);
    read(N);
    read(G);
    LL ans=0;
    solveB::solve();
    for(int i=1;i*2<=N;i++)
        if(gcd((int)N,i)==1)
        {
            ans+=solveB::combin(G,i);
            if(ans>=MOD)
                ans-=MOD;
            ans+=solveB::combin(G,N-i);
            if(ans>=MOD)
                ans-=MOD;
        }
    LL sum=0;
    sum=solveB::qpow(N,ans,mod);
    sum=sum*solveB::qpow(N,27092310,mod)%mod;
    printf("%lld",sum);
}