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