#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 0;
	}
	if (y % 2 == 0) {
		unsigned long long int product = (x % mod) * (x % mod);
		product %= mod;
		return power(product, y / 2, mod) % mod;
	}
	else {
		unsigned long long int product = (x % mod) * (x % mod);
		product %= mod;
		return ((x % mod) * (power(product, y / 2, mod) % mod)) % mod;
	}
}
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;

}