#include <fstream>

using namespace std;

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

const int MAXN = 2e9;
const int MAXA = 2e9;

int a, n;

int fi(int nr) {
	int ret = nr;
	int aux = nr;

	if (nr % 2 == 0) {
    ret /= 2;
    ret *= (2 - 1);
    while (nr % 2 == 0)
      nr /= 2;
	}

	for (int i = 3; i * i <= aux; i += 2) {
		if (nr % i == 0) {
			ret /= i;
			ret *= (i - 1);
			while (nr % i == 0) nr /= i;
		}
	}

  if (nr > 1)
    ret = nr - 1;

	return ret;
}

int put(int a, int b) {
	int ret = 1;

	while (b) {
		if (b & 1) ret = 1LL * ret * a % n;
		a = 1LL * a * a % n;
		b >>= 1;
	}

	return ret % n;
}

int invm(int a, int n) {
	return put(a, fi(n) - 1);
}

int main() {
	in >> a >> n;
	out << invm(a, n);

	return 0;
}