题意：求 $g^{\sum\limits_{k|n}(\begin{matrix}n\\k\end{matrix})}\%999911659$ 的值。求大佬调一下 /bx

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=35617;
int n,g,fac[N+1][4],ifac[N+1][4];
const int b[]={2,3,4679,35617};
vector<int> valist;
#define pb push_back
int inv(int x,int p){
  if(x==1) return 1;
  return(p-x/p)*1ll*inv(p%x,p)%p;
}
void init(){
  for(int i=*fac[0]=fac[0][1]=fac[0][2]=fac[0][3]=1;i<=N;++i)
    for(int j=0;j<4;++j) fac[i][j]=1ll*fac[i-1][j]*i%b[j];
  for(int i=0;i<4;++i) ifac[N][i]=inv(fac[N][i],b[i]);
  for(int i=N-1;i;--i) for(int j=0;j<4;++j)
    ifac[i][j]=1ll*ifac[i+1][j]*(i+1)%b[j]; 
  valist.pb(1);
  if(n==1) return;
  for(int i=2;i*i<=n;++i)
    if(n%i==0) valist.pb(i);
  valist.pb(n); 
}
int C(int n,int m,int t){
  assert(t>=0&&t<4); assert(n>=m);
  return 1ll*fac[n][t]*ifac[m][t]%b[t]*ifac[n-m][t]%b[t];
}
ll Lucas(int n,int m,int t){
  return n<m?0:!n?1:Lucas(n/b[t],m/b[t],t)*C(n%b[t],m%b[t],t)%b[t];
}
int lucas(int t){
  int ans=0;
  for(int x:valist)
    ans=(1ll*ans+Lucas(n,x,t))%b[t];
  return ans;
}
const int P=999911659;
int crt(){
  ll S=0,h=1,a;
  for(int i=0;i<4;h*=b[i++])
    for(a=lucas(i);S%b[i]!=a;S=(S+h)%P);
  return S;
}
int qpow(int a,int b){
  int res=1;
  for(;b;b>>=1,a=1ll*a*a%P)
    if(b&1) res=1ll*res*a%P;
  return res;
}
main(){
  cin>>n>>g;
  if(g%P==0) puts("0");
  else cout<<qpow(g,crt());
}