#include<cstdio>
int main()
{
    long long n,a,s,d,p,cn;
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld%lld",&a,&n);
    s=n;
    cn=n;
    d=2;
    while(d*d <= n)
    {
        p=0;
        while(n%d==0)
        {
            n/=d;
            p++;
        }
        if(p>1)
            s=s/p*(p-1);
        d++;
    }
    if(n != 1)
        s = s/n*(n-1);

    n=s-1;
    p=1;
    while(n!=0)
    {
        if(n%2!=0)
            p=p*a%cn;
        a=a*a%cn;
        n/=2;
    }
    printf("%lld\n",p);
    return 0;
}