#include<cmath>

#include<cstdio>

#include<iostream> 

using namespace std;

const int mod=;

const int phi=mod-;

typedef long long LL;

int p[];

LL mul[][];

LL c[];

void pre()

{

    p[]=;

    p[]=;

    p[]=;

    p[]=;

    for(int i=;i<=;++i)

    {

        mul[i][]=;

        for(int j=;j<=;++j)  mul[i][j]=mul[i][j-]*j%p[i];

    }

}

LL gcd(LL a,LL b)

{

    return !b ? a : gcd(b,a%b);

}

LL Pow(LL a,LL b,LL mod)

{

    LL ans=;

    for(;b;a=a*a%mod,b>>=)

        if(b&) ans=ans*a%mod;

    return ans;

}

LL C(LL n,LL m,int i)

{

    if(m>n) return ;

    return mul[i][n]*Pow(mul[i][m],p[i]-,p[i])%p[i]*Pow(mul[i][n-m],p[i]-,p[i])%p[i];

}

LL Lucas(LL n,LL m,int i)

{

    if(m>n) return ;

    LL ans=;

    for(;m;n/=p[i],m/=p[i]) ans=(ans*C(n%p[i],m%p[i],i))%p[i];

    return ans;

}

void exgcd(LL a,LL b,LL &x,LL &y)

{

    if(!b) x=,y=;

    else exgcd(b,a%b,y,x),y-=a/b*x;

}

int main()

{

    pre();

    LL n,g;

    cin>>n>>g;

    if(gcd(g,mod)!=)

    {

        printf("");

        return ;

    }

    int m=sqrt(n);

    for(int i=;i<=m;++i)

        if(n%i==)

        {

            for(int j=;j<=;++j) c[j]=(c[j]+Lucas(n,i,j))%p[j];

            if(n/i!=i)

            for(int j=;j<=;++j) c[j]=(c[j]+Lucas(n,n/i,j))%p[j];

        }

    LL ans=;

    LL Mi,mi,x,y;

    for(int i=;i<=;++i)

    {

        Mi=phi/p[i];

        mi=p[i];

        exgcd(Mi,mi,x,y);

        x=(x%mi+mi)%mi;

        if(!x) x+=mi;

        ans+=c[i]*Mi*x;

    }

    ans=Pow(g,ans,mod);

    cout<<ans;

}