蒟蒻求救

#include<bits/stdc++.h>
#define Mod 999911658
using namespace std;
typedef long long ll;
ll n,p;
ll c[205],sum,jc[50000];//n的约数 
ll a[5],m[5]={0,2,3,4679,35617};//模数 

ll quickpow(ll a,ll b,ll mod)
{
    ll ret=1LL;
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ret;
}
ll C(ll n,ll m,ll mod)
{
    if(n<m) return 0;
    ll jcn=jc[n],jcm=jc[m]*jc[n-m]%mod;
    return jcn*quickpow(jcm,mod-2,mod)%mod;
}
ll Lucas(ll n,ll m,ll mod)
{
    if(n<m) return 0LL;
    if(!m||!n) return 1LL;
    return C(n%mod,m%mod,mod)*Lucas(n/mod,m/mod,mod)%mod;
}
void init(int x)
{
    jc[0]=1LL;
    for(ll i=1;i<=m[x];++i) 
    jc[i]=jc[i-1]*i%m[x];
}
void work(int x)//求cigema(d|n, C(n,d) )%m[x] 
{
    ll ret=0LL;
    init(x);//求阶乘
    for(int i=1;i<=sum;++i)
    ret=(ret+Lucas(n,c[i],m[x]))%m[x];
    a[x]=(ret+m[x])%m[x];
}
ll crt()//合并四个答案
{
    ll ret=0LL;
    for(int i=1;i<=4;++i) 
    ret=(ret+a[i]%Mod*(Mod/m[i])%Mod*quickpow(Mod/m[i],m[i]-2,m[i]))%Mod;
    return ret;
}

int main()
{
    cin>>n>>p;
    if(p%(Mod+1)==0) {cout<<0<<endl; return 0;}//特判 
    for(int i=1;i*i<=n;++i)//分解质因数 
    {
        if(n%i==0)
        {
            c[++sum]=i;
            if(i*i!=n) c[++sum]=n/i;
        }
    }
    for(int i=1;i<=4;++i) work(i);//分别求四个答案
    ll b=(crt()+Mod)%Mod;
    cout<<quickpow(p,b,Mod+1)<<endl;
    return 0;
}