#include <cstdio>
using namespace std;
long long int a,n,d,p,nr,aux;
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld %lld\n",&a,&n);
    nr=n;
    p=n;
    for(d=2;d*d<=n;d++)
        if(!(n%d))
        {
            while(n%d==0)
                n/=d;
            p=(p/d)*(d-1);
            if(n==1)
                break;
        }
    if(n!=1)
        p=(p/n)*(n-1);
    p--;
    d=1;
    while(p)
    {
        if(p%2==1)
            d=(d*a)%nr;
        a=(a*a)%nr;
        p/=2;
    }
    printf("%lld\n",d);
    return 0;
}