古代猪文

题意：
给定整数，计算

思路：
若，则上式为0。否则互质，可以用欧拉降幂:
较大，可以考虑用定理

定理要求模数是质数，尝试分解质因数，发现。

MyCode：

```#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7,maxm=2e5+7,mod=999911659;
typedef long long int ll;
#define eb emplace_back
#define ef emplace_front
#define ep emplace
#define fi first
#define se second
ll inf[100005];
ll qpow(ll a,ll b,ll p) {
    ll res=1;
    while(b) {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
ll China(int n,ll *m,ll *a,ll M) {
    ll Mi,x(0);
    for(int i=0; i<n; i++) {
        Mi=M/m[i];
        x=(x+qpow(Mi,m[i]-2,M)*Mi*a[i])%M;
    }
    return (x+M)%M;
}
ll c(ll n,ll m,ll p) {
    if(n<m) return 0;
    return inf[n]*qpow(inf[n-m]*inf[m]%p,p-2,p)%p;
}
ll lucas(ll n,ll m,ll p) {
    if (n<m) return 0;
    if (!n) return 1;
    return lucas(n/p,m/p,p)*c(n%p,m%p,p)%p;
}
ll a[4],b[4]= {2,3,4679,35617};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll q,n;
    cin>>n>>q;
    if(q%mod==0)
        return cout<<"0\n",0;
    inf[0]=inf[1]=1;
    for(int i=0; i<4; ++i) {
        for(int j=2; j<=b[i]; ++j) inf[j]=inf[j-1]*j%b[i];
        for(ll j=1; j*j<=n; ++j) if(n%j==0){
            a[i]=( a[i]+lucas(n,j,b[i]) )%b[i];
            if(j*j!=n) a[i]=( a[i]+lucas(n,n/j,b[i]) )%b[i];
        }
    }
    cout<<qpow(q,China(4,b,a,mod-1),mod)<<'\n';
    return 0;
}