#include <iostream>
#include <fstream>
#include <stdint.h>

int main() {
	std::ifstream fin("inversmodular.in");
	std::ofstream fout("inversmodular.out");

	int64_t a, n;
	fin >> a >> n;

	int64_t exp = n, cop = n;
	for(int64_t d = 2; d * d <= cop; ++d) {
		if(cop % d)
			continue;
		
		while(!(cop % d))
			cop /= d;
		exp = (exp / d) * (d - 1);
	}
	if(cop != 1)
		exp = (exp / cop) * (cop - 1);
	
	--exp;
	int64_t x = 1, val = a;
	for(; exp; exp >>= 1) {
		if(exp & 1) {
			x *= val;
			x %= n;
		}
		val *= val;
		val %= n;
	}

	fout << x;

	fin.close();
	fout.close();

	return 0;
}