#include <iostream>
#include <fstream>
#include <unordered_map>

using namespace std;

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

unordered_map <long long int, long long int> frecv;

bool ok = 0;

long long int fast(long long int x, long long int n)
{
	if (n < 0)
		return fast(1 / x, -n);
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return fast(x * x, n / 2);
	if (n % 2 == 1)
		return x * fast(x * x, (n - 1) / 2);
}

void prim(long long int n)
{
	while (n % 2 == 0)
	{
		frecv[2]++;
		ok = 1;
		n = n / 2;
	}

	for (long long int i = 3; i * i <= n; i+=2)
	{
		while (n % i == 0)
		{
			ok = 1;
			frecv[i]++;
			n = n / i;
		}
	}
	if (n > 2) {
		frecv[n]++;
	}
}

int main()
{
	long long int n, x, A, sum = 0, p = 1;
	in >> A >> n;
	prim(n);
	if (ok == 0)
		p = n - 1;
	else
	{
		for (auto i : frecv)
		{
			sum = 0;
			sum = fast(i.first, i.second);
			sum -= fast(i.first, i.second - 1);
			p *= sum;
			p = p % n;
		}
	}
	out << fast(A, p - 1) % n;
}