#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int main()
{
    long long 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 && n>1)
    {
        while(n%p==0)
        {
            e++;
            n=n/p;
        }
        if(e)
            phi=phi/p*(p-1);
        p++;
        e=0;
    }
    if(n>1)
        phi=phi/n*(n-1);
    phi--;
    p=1;
    while(phi)
    {
        if(phi&1)
            p=(p*a)%cn;
        a=(a*a)%cn;
        phi=phi/2;
    }
    out<<p;
    return 0;
}