#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long n,a,m,e,i,d;
void extract();
int main()
{
    f>>a>>n;
    e=1;
    m=n;
    d=2;
    if(m%d==0)
        extract();
    for(d=3;d*d<=m;d++)
        if(m%d==0)
            extract();
    if(m>1)
        e*=m-1;
    e--;
    i=1;
    while(e)
    {
        if(e%2)
            i=(i*a)%n;
        a=(a*a)%n;
        e/=2;
    }
    g<<i;
    return 0;
}
void extract()
{
    e*=d-1;m/=d;
    while(m%d==0)
    {
        e*=d;
        m/=d;
    }
}