#include <iostream>
#include <fstream>
#define ull unsigned long long

using namespace std;
ull n,x,a;
ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");
ull pow(ull x, ull n, ull MOD)
{
    ull y=x,sol=1;
    while (n)
    {
        if ((1&n)>0) sol=(sol*y)%MOD;
        y=(y*y)%MOD;
        n/=2;
    }
    return sol;
}
ull phi (ull n)
{
    ull i,sol=n;
    for (i=2;i*i<=n;i++)
    {
        if (n%i==0)
        {
            while (n%i==0) n/=i;
            sol=(sol/i)*(i-1);
        }
    }
    if (n!=1) sol=sol/n*(n-1);
    return sol;
}
int main()
{
    f>>a>>n;
    g<<pow(a,phi(n)-1,n);
    return 0;
}