#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=4e4+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
    return x*f;
}

int n,g;
int P[5]={999911659,2,3,4679,35617};
int Pow(ll a,int b,int P){
    ll re=1;
    for(;b;b>>=1,a=a*a%P)
        if(b&1) re=re*a%P;
    return re;
}
int Inv(int a,int P){return Pow(a,P-2,P);}
int inv[N][5],fac[N][5],facInv[N][5];
void ini(){
    for(int j=1;j<=4;j++){
        int MOD=P[j];
        inv[1][j]=fac[0][j]=facInv[0][j]=1;
        for(int i=1;i<=MOD;i++){
            if(i!=1) inv[i][j]=-MOD/i*inv[MOD%i][j]%MOD;
            if(inv[i][j]<0) inv[i][j]+=MOD;
            fac[i][j]=fac[i-1][j]*i%MOD;
            facInv[i][j]=facInv[i-1][j]*inv[i][j]%MOD;
        }
    }
}
inline int C(int n,int m,int j){
    int p=P[j];
    return fac[n][j]*facInv[m][j]%p*facInv[n-m][j]%p;
}
int lucas(int n,int m,int j){
    int MOD=P[0]-1,a=1,p=P[j];
    for(;m;m/=p,n/=p) a=a*C(n%p,m%p,j)%p;
    return (ll)a*(MOD/p)%MOD*Inv(MOD/p,p)%MOD;
}
ll Lucas(ll n,ll m){
    ll re=0,MOD=P[0]-1;
    for(int i=1;i<=4;i++)
        re=(re+lucas(n,m,i))%MOD;
    return re;
}
ll solve(){
    int m=sqrt(n);
    ll re=0;
    for(int i=1;i<=m;i++) if(n%i==0){//printf("hi %d\n",i);
        re=(re+Lucas(n,i))%(P[0]-1);//printf("Lucas %d\n",Lucas(n,i));
        if(i*i!=n) re=(re+Lucas(n,n/i))%(P[0]-1);//printf("hi %d\n",n/i);
    }
    return re;
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int main(){
    freopen("in","r",stdin);
    n=read();g=read();
    if(gcd(g,P[0])!=1){puts("0");return 0;}
    ini();
    //printf("solve %d\n",solve());
    printf("%d",Pow(g,solve(),P[0]));
}