#include<fstream>
#include<limits.h>
#include<math.h>

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 power(int x, int y, int mod) {
	if (y == 0) {
		return 1;
	}
	int aux = 1;
	while (y > 0) {
		if (y % 2) {
			unsigned long long int product = ((unsigned long long int)aux % mod) * ((unsigned long long int)x % mod);
			aux = product % mod;
		}
		unsigned long long int product = (((unsigned long long int)x % mod) * ((unsigned long long int)x % mod));
		x = product % mod;
		y = y / 2;
	}
	return aux;
}
int main() {
	int A, N;
	cin >> A >> N;
	int prim = prime(N);
	if (prim) {
		p = N - 1;
	}
	else {
		p = phi(N);
	}
	int i = power(A, p - 1, N);
	cout << i;
	return 0;

}