#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int v[1005];
int main()
{
    int a,cn,n,x=1,i,p=2,e,s,phi;
    in>>a>>n;
    s=1;
    phi=n;
    cn=n;
    e=0;
    while(p*p<=n)
    {
        if(n%p==0)
            phi=phi*(p-1)/p;
        while(n%p==0)
        {
            e++;
            n=n/p;
        }
        p++;
        e=0;
    }
    if(n>1)
        phi=phi*(n-1)/n;
    phi--;
    p=1;
    while(phi)
    {
        if(phi&1)
            p=(p*a)%cn;
        a=a*a;
        phi=phi/2;
    }
    out<<p;
    return 0;
}