#include<cstdio>
using namespace std;
long long A,N,phi,i,sol,MOD;
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld%lld",&A,&N); phi=1; MOD=N;
    for(i=2;i*i<=N;i++)
        if(N%i==0)
        {
            while(N%i==0)
            {
                phi*=i;
                N/=i;
            }
            phi/=i; phi*=i-1;
        }
    if(N>1) phi*=N-1;
    phi--; sol=1;
    for(i=1;i<=phi;i<<=1)
    {
        if(i&phi) sol=(sol*A)%MOD;
        A=(A*A)%MOD;
    }
    printf("%lld\n",sol);
    return 0;
}