//By SiriusRen

#include <cmath>

#include <cstdio>

using namespace std;

#define int long long

const int M=,N=;

void exgcd(int a,int b,int &x,int &y){

    if(!b){x=,y=;return;}

    exgcd(b,a%b,x,y);

    int temp=x;x=y;y=temp-a/b*y;

}

int CRT(int *a,int *m,int num){

    int ans=;

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

        int x,y;

        exgcd(M/m[i],m[i],x,y);

        ans=(ans+M/m[i]*x%M*a[i])%M;

    }return ans;

}

int power(int x,int y){

    int ans=;

    while(y){

        if(y&)ans=ans*x%(M+);

        x=x*x%(M+),y>>=;

    }return ans;

}

int m[]={,,,,},n,g,fac[N],inv[N],sqr,s[N],top,ans[],T;

int C(int x,int y){

    if(x<y)return ;

    if(x<m[T]&&y<m[T])return fac[x]*inv[y]%m[T]*inv[x-y]%m[T];

    return C(x/m[T],y/m[T])*C(x%m[T],y%m[T])%m[T];

}

signed main(){

    scanf("%lld%lld",&n,&g),sqr=sqrt(n);

    for(int i=;i<sqr;i++)if(n%i==)s[++top]=i,s[++top]=n/i;

    if(sqr*sqr==n)s[++top]=sqr;

    if(n%sqr==&&sqr*sqr!=n)s[++top]=sqr,s[++top]=n/sqr;

    fac[]=fac[]=inv[]=inv[]=;

    for(T=;T<=;T++){

        for(int i=;i<m[T];i++)fac[i]=fac[i-]*i%m[T];

        for(int i=;i<m[T];i++)inv[i]=(m[T]-m[T]/i)*inv[m[T]%i]%m[T];

        for(int i=;i<m[T];i++)inv[i]=inv[i]*inv[i-]%m[T];

        for(int i=;i<=top;i++)ans[T]=(ans[T]+C(n,s[i]))%m[T];

    }

    printf("%lld\n",power(g,CRT(ans,m,)+M));

}