#include <iostream>
#include <fstream>
using namespace std;

struct factor
{
	long long base, exponent;
} FACT[169];
int nrf;

bool isPrime(long long x)
{
	if (x <= 1)
		return false;
	if (x == 2)
		return true;
	if (x % 2 == 0)
		return false;
	for (long long d = 3; d * d <= x; d += 2)
		if (x % d == 0)
			return false;
	return true;
}

long long exponentiere(long long A, long long P, long long MOD)
{
	int result = 1;
	while (P > 0)
		if (P % 2 == 0)
			A = (A * A) % MOD, P /= 2;
		else
			result = (result * A) % MOD, --P;
	return result % MOD;
}

void factorizare(long long n)
{
	long long d = 2;
	while (n > 1)
		if (d * d > n)
			++nrf, FACT[nrf].base = n, FACT[nrf].exponent = 1, n = 1;
		else
			if (n % d == 0)
			{
				int power = 0;
				while (n % d == 0)
					++power, n /= d;
				++nrf;
				FACT[nrf].base = d, FACT[nrf].exponent = power;
			}
			else
				++d;
}

int main()
{
	ifstream fi("inversmodular.in");
	ofstream fo("inversmodular.out");
	long long A, N; fi >> A >> N;
	if (isPrime(A)) // calculam A ^ (N - 2) % N
		fo << exponentiere(A, N - 2, N);
	else
	{
		int result = 1;
		factorizare(N);
		for (int i = 1; i <= nrf; ++i)
			result = result * (exponentiere(FACT[i].base, FACT[i].exponent, N) * exponentiere(FACT[i].base, FACT[i].exponent - 1, N)) % N;
		fo << result;
	}
	return 0;
}