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