#include <iostream>
#include <fstream>
#define LL long long
using namespace std;

/*int main()
{
    int x;
    cin>>x;
    cout << "Hello world!" << endl;
    return 0;
}*/

LL N,M;
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;
}

int main()
{
	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	cin>>N>>M;
    LL put = getphi(M) - 1;
	LL nr = N;
	LL crt = 1;
    for(LL p = 1;p <= put;p <<= 1)
    {
	 	if (p & put) crt = (crt * nr) % M;
	  	nr = (nr * nr) % M;
	}
    g<<crt;
	return 0;
}