#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;
    f=n;
    v=0;
    while(x%2==0)
    {
        x/=2;
        v=1;
    }
    if(v==1)f=f*(d-1)/d;
    for(i=3; i*i<=x && x>1; i++)
    {
        if(x%i==0)
        {
            while(x%i==0)
            {
                x/=i;
                v=1;
            }
            f=f*(i-1)/i;
        }
    }
    if(n>1)
        f=f*(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;
}