#include <bits/stdc++.h>
using namespace std;
#define LL long long
long long N;
LL M,P;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

LL getphi(LL nr)
{
	LL cur = nr;
	for(LL i = 2;i * i <= nr; ++i)
	{
		if (nr % i == 0)
		{
			while(nr % i == 0)nr /= i;
			cur = (cur / i) * (i - 1);
		}
	}
        if (nr != 1) cur = cur / nr * (nr - 1);
	return cur;
}


LL binary_exp(LL a , LL b){
    long long p = 1;
    for(LL i=1 ; i<=b ; i <<=1){
        if(i&b){
            p=(p * a) % P;
        }
        a=(a*a) % P;
    }
    return p;
}
LL invmod(LL a,LL b){
    N = getphi(b) - 1;
    return binary_exp(a,N) % b;
}


int main()
{
f >> M >> P;
g << invmod(M,P);


}