#include <bits/stdc++.h.>
using namespace std;

typedef long long ll;

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

ll n, p, k = 1;

unsigned long long lgpower(int n, int h)
{
	ll sol = 1;
	
	for (int i = 0; (1 << i) <= h; ++i)
	{
		if (((1 << i) & h) > 0)
			sol = (sol * n) % p;
		n = (n * n) % p;
	}
	return sol;
}

bool prim(ll n)
{
	for (int i = 2; i < n; i++)
		if (n % i == 0 || n == 0 || n == 1)
			return 0;
	return 1;
}

int main()
{
	fin >> n >> p;
	ll x = p;
	ll i = 2;
	if (prim(p))
	{
		fout << lgpower(a, n - 2);
		return 0;
	}
	while (x != 1)
	{ 
		while (x % i == 0)
		{
			ll t = x;
			ll nr = 0;
			while (t % i == 0)
			{
				nr++;
				t /= i;
			}
			k *= lgpower(i, nr - 1) * (i - 1);
			k %= p;
			x /= i * nr;
		}
		i++;
	}
	fout << lgpower(n, k - 1);
}