#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a,n,f=1,i,d,x,v,p;
int main()
{
    fin>>a>>n;
    d=2;
    x=n;
    v=0;
    while(x%2==0)
    {
        x/=2;
        v=1;
    }
    if(v==1)f=f*n*(d-1)/d;
    for(i=3;i*i<=x && x>1;i++)
    {
        v=0;
        while(x%i==0)
        {
            x/=i;
            v=1;
        }
        if(v==1)f=f*n*(i-1)/i;
    }
    if(n>1)
        f=f*n*(n-1)/n;
    f--;
    p=1;
    while(f>0)
    {
        if(f%2==1)
        {
            f--;
            p=(p*a)%n;
        }
        else
        {
            p=(p*p)%n;
            f/=2;
        }
    }
    fout<<p;
    return 0;
}