#include<fstream>

using namespace std;

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

int p;

int prime(int n) {

	if (n == 0 || n == 1) {
		return 0;
	}
	if (n % 2 == 0) {
		return n == 2;
	}
	for (int i = 3; i * i <= n; i += 2) {
		if (n % i == 0) {
			return 0;
		}
	}
	return 1;
}
int phi(int n) {
	int result = n;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			while (n % i == 0)
				n /= i;
			result -= result / i;
		}
	}
	if (n > 1)
		result -= result / n;
	return result;
}

int main() {
	int A, N;
	cin >> A >> N;
	if (prime(N)) {
		p = N - 1;
	}
	else {
		p = phi(N);
	}
	p = (int)pow(A, p - 1) % N;
	cout << p;
	return 0;

}