题解：

一看就是一道数学题了。

根据欧拉定理，必须要处理的是$sum_i|n C(n,i)\space mod \space \phi(p)$

令A等于这个大式子。

phi(p)=999911658=2*3*4679*35617

是四个质数的乘积。

看来就类似扩展LUCAS了。

但是，指数只有1

所以，我们可以求出：

A = a1 mod 2

A = a2 mod 3

A = a3 mod 4679

A = a4 mod 35617

（a1~a4怎么求？LUCAS定理即可。）

这是一个同余方程，要解出A

其实，我们就要A = a5 mod 999911658

中国剩余定理合并，返回a5即可。

不会CRT？右转：

注意，求的A是在mod 999911658下的。不能用其他质数mod完。除了ti，即Mi在mod mi下的逆元。

 

最后计算G^a5 mod 999911659

但是，出题人比较狡诈，还是有坑的。

因为，欧拉定理的适用的前提是：gcd(G,mod)=1;

扩展欧拉定理更是如此。

如果G=mod，那么就不互质了。

如果这时候，恰好a5=0，那么我们会输出1

其实答案无论如何是0

G=mod判掉即可。

 

代码：

#include
     
      using namespace std;typedef long long ll;const int N=35666;const int mod=999911659;const int P[4]={
   2,3,4679,35617};ll jie[4][N],inv[4][N];ll f[4][2];ll n,g;ll qm(ll x,ll y,ll p){    ll ret=1%p;    while(y){        if(y&1) (ret*=x)%=p;        (x*=x)%=p;        y>>=1;    }    return ret;}ll C(ll a,ll b,ll id){    //if(b==0) return 1;    ll ret=jie[id][a]*inv[id][a-b]%P[id]*inv[id][b]%P[id];    //cout<<" C "<
      <<" "<<<" "<
        
         <<" "<
         
          <<" : "<
          
           <<" "<
           
            <<" "<
            
             <<" "<
             
              <