#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long 
#define ull unsigned long long 
#define nmax 6000006
#define MOD 1999999973 
#define INF 9973
//#define fin cin 
//#define fout cout 

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int n, mod;

int Phi(int x)
{
	int f, p;
	p = x;
	for (f = 2; f * f <= x; f++)
		if (x % f == 0)
		{
			p = p / f * (f - 1);
			while (x % f == 0)
				x /= f;	
		}
	if (x > 1)
		p = p / x * (x - 1);
	return p;
}

int Put(int x, int exp, int mod)
{
	if (exp == 0)
		return 1;
	if (exp % 2 != 0)
		return 1ll * x * Put(x, exp - 1, mod) % mod;
	int P = Put(x, exp / 2, mod);
	return 1ll * P * P % mod;
}

int main()
{
	int phi;
	fin >> n >> mod;
	phi = Phi(mod);
	fout << Put(n, phi - 1, mod);
	fin.close();
	fout.close();
	return 0;
}