#include <fstream>

using namespace std;
ofstream fout("inversmodular.out");

long long a, n;
long long exp_rapida(long long a, long long phi);

int main()
{
	freopen("inversmodular.in", "r", stdin);
	scanf("%d%d", &a, &n);
	long long d = 2;
	long long cn = n;
	long long phi = n - 1;
	for (long long i = 2; i*i <= n; i++)
		if (!(n%i))
		{
			phi -= phi / i;
			while (!(n%i)) n /= i;
		}
	if (n>1) phi -= phi / n;
	n = cn;
	fout << exp_rapida(a, phi - 1) << '\n';
	return 0;
}

long long exp_rapida(long long a, long long phi)
{
	long long ans = 1;
	long long pw = a;
	for (long long i = 1; i <= phi; i <<= 1)
	{
		if (i & phi)
			ans = (ans * pw) % n;
		pw *= pw;
		pw %= n;
	}
	return ans;
}