#include <fstream>
using namespace std;

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

int N, mod;

int phi(int N) {
	int answer = N; 
	for (int i = 2; i * i <= N; i++) {
		int putere = 0; 
		while (N % i == 0) {
			putere++; 
			N /= i; 
		}

		if(putere > 0)
			answer -= answer / i; 
	}

	if (N != 1)
		answer -= answer / N; 

	return answer; 
}

int lgput(int baza, int exp, int mod) {
	int answer = 1; 
	while (exp) {
		if (exp % 2 == 1) {
			answer = (1LL * answer * baza) % mod; 
		}
		baza = (1LL * baza * baza) % mod; 
		exp /= 2; 
	}

	return answer; 
}

int invers_modular(int a, int mod) {
	return lgput(a, phi(mod) - 1, mod); 
}


int main()
{
	fin >> N >> mod;
	int answer = invers_modular(N, mod);
	fout << answer; 

	return 0;
}