#include <fstream>
#include <cmath>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long a, n, r, f, cn;

long long Lgput(long long a, long long x)
{
    long long act, sol=1;
    act=a;
    while (x>0)
    {
        if (x%2==1)
        {
            sol *= act;
            sol %= cn;
        }
        act = (act*act)%cn;
        x=x/2;
    }
    return sol%cn;
}

int main()
{
    long long i;
    fin>>a>>n;
    cn=n;
    r=sqrt(n);
    f=n;
    for (i=2; i<=r; i++)
    {
        if (n%i==0)
        {
            while (n%i==0)
                n=n/i;
            f-=f/i;
        }
    }
    if (n!=1)
        f-=f/n;
    fout<<Lgput(a, f-1);
    return 0;
}