#include<cstdio>
int a,n,i,f,x,y,r,sol;
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d%d",&a,&n);
    for(i=2;i<=n-1;i++)
    {
        x=n; y=i;
        if(x%y==0) continue;
        while(x%y)
        {
            r=x%y;
            x=y;
            y=r;
        }
        if(y==1) f++;
    }
    sol=1;
    for(i=1,x=a;i<=f;i=i<<1,x*=x)
    {
        if(i&f) sol*=x;
        if(sol>n) sol%=n;
    }
    printf("%d",sol);
    return 0;
}