\(Description\)

给定N,G，求\[G^{\sum_{k|N}C_n^k}\mod\ 999911659\]

\(Solution\)

由费马小定理，可以先对次数化简，即求\(\sum_{k|N}C_n^k\mod\ 99991168\)，然后快速幂就可以解决。

可以把999911659分解成4个质因数，分别用Lucas定理求解然后用CRT合并即可。

要注意费马小定理成立的条件: a,p互质，即G!=mod.

//1380kb    156ms#include 
    
     #include 
     
      #include 
      
       #define P (999911658)#define mod (999911659)typedef long long LL;const int Pi[5]={2,3,4679,35617};int cnt,divi[100005],r[5],fac[40000];int FP(LL x,int k,LL p){    LL t=1;    for(; k; k>>=1,x=x*x%p)        if(k&1) t=t*x%p;    return (int)t;}inline int inv(int v,int p){    return FP(v,p-2,p);}inline int C(int n,int m,int p){    if(n