记录编号	390095	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]艾米利亚的魔法	最终得分	100
用户昵称	卜卜	是否通过	通过
代码语言	C++	运行时间	3.390 s
提交时间	2017-04-01 20:34:51	内存使用	5.11 MiB

//Okazaki Tomoya 
//1.048596  Okabe Rintarou
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<queue>
#include<cmath>
using namespace std;

inline int getint()
{
    static int x; static bool f; static char c;
    x=0,f=0; do {c=getchar(); if(c=='-') f=1;} while(c<'0'||c>'9');
    while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return f?-x:x;
}

typedef long long LL;
const int maxn=1000002;
const int maxup=129013;
int jc[maxup],jcn[maxup];
int n,g,pre[10],tot,num[maxn],L,mod;
inline int add(int a,int b) {a+=b; return a>=mod?a-mod:a<0?a+mod:a;}
inline int mul(int a,int b) {return (LL)a*b%mod;}
inline int pow(int d,int k)
{
    static int ans;
    ans=1; while(k) {
        if(k&1) ans=mul(ans,d);
        k>>=1; d=mul(d,d);
    } return ans;
}
inline void prepare()
{
    static int i;
    for(i=2;i<mod;++i) jc[i]=mul(jc[i-1],i);
    jcn[mod-1]=pow(jc[mod-1],mod-2);
    for(i=mod-2;i>1;--i) jcn[i]=mul(jcn[i+1],i+1);
}
inline int C(int n,int m)
{
    if(n<m) return 0;
    else if(m==n) return 1;
    return mul(jc[n],mul(jcn[m],jcn[n-m]));
}
int Lucas(int n,int m)
{
    if(m==0) return 1;
    return mul(C(n%mod,m%mod),Lucas(n/mod,m/mod));
}
inline void exgcd(int a,int b,int &x,int &y)
{
    if(b==0) {x=1,y=0; return;}
    exgcd(b,a%b,y,x); y-=a/b*x;
}

int main()
{
    freopen("aimiliyademagic.in","r",stdin),freopen("aimiliyademagic.out","w",stdout);
    n=getint(),g=getint(); int i,j,N;
    for(N=n,j=sqrt(n+0.5),i=2;i<=j;++i)
        if(!(N%i)) {
            pre[++tot]=i;
            do {N/=i;} while(!(N%i));
        }
    if(N>1) pre[++tot]=N; num[L=1]=1;
    for(i=2,N=min(n,g);i<=N;++i) {
        for(j=1;j<=tot;++j)
            if(!(i%pre[j]))
                break;
        if(j>tot) num[++L]=i;
    }

    int A[5],x,y,now; jc[0]=jc[1]=jcn[0]=jcn[1]=1;
    mod=2,A[0]=0; prepare(); for(i=1;i<=L;++i) A[0]=add(A[0],Lucas(g,num[i]));
    mod=3,A[1]=0; prepare(); for(i=1;i<=L;++i) A[1]=add(A[1],Lucas(g,num[i]));
    mod=5,A[2]=0; prepare(); for(i=1;i<=L;++i) A[2]=add(A[2],Lucas(g,num[i]));
    mod=7,A[3]=0; prepare(); for(i=1;i<=L;++i) A[3]=add(A[3],Lucas(g,num[i]));
    mod=129011,A[4]=0; prepare(); for(i=1;i<=L;++i) A[4]=add(A[4],Lucas(g,num[i]));

    //CRT
    now=A[0];
    mod=6; exgcd(3,2,x,y); now=add(mul(now,mul(3,x)),mul(2,mul(y,A[1])));
    mod=30; exgcd(5,6,x,y); now=add(mul(now,mul(5,x)),mul(6,mul(y,A[2])));
    mod=210; exgcd(7,30,x,y); now=add(mul(now,mul(7,x)),mul(30,mul(y,A[3])));
    mod=27092310; exgcd(129011,210,x,y); now=add(mul(now,mul(129011,x)),mul(210,mul(y,A[4])));
    mod=27092311; now=pow(n,now);

    mod=54184622; exgcd(2,27092311,x,y); now=add(mul(now,mul(2,x)),mul(27092311,mul(y,n&1)));
    printf("%d\n",now);
    //printf("\n%.4lf",(double)clock() / CLOCKS_PER_SEC);
    return 0;
}