#include <iostream>
#include <fstream>
using namespace std;
long long a,m,x;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
void citire()
{
    f>>a>>m;
}
long long phi(long long nr)
{long long c=nr;
for(long long i=2;i*i<=nr;i++)
{
    if(nr%i==0)
    {
        while(nr%i==0)nr=nr/i;
        c=(c/i)*(i-1);
    }

}
if(nr!=1)c=c/nr*(nr-1);
return c;
}
long long invm(long long j)
{x=phi(m)-1;
long long nr=j;
    long long c=1;
    for(long long i=1;i<=x;i<<=1)
    {
        if(i&x)c=(c*nr)%m;
        nr=(nr*nr)%m;

    }
    return c;

}
int main()
{
    citire();
    g<<invm(a);
    return 0;
}