#include <iostream>
#include <fstream>

using namespace std;

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

long long putere(int n, int p, int modulo) {
	if (p == 0) return 1;

	long long aux = putere(n, p / 2, modulo);
	aux = (aux * aux) % modulo;
	if (p % 2 == 1) aux = (aux * n) % modulo;
	return aux;
}

int fi(int x) {
	int fi = x;

	for (int d = 2; d * d <= x; d++) {
		if (x % d != 0) continue;
		while (x % d == 0) x /= d;
		fi = fi / d * (d - 1);
	}

	if (x != 1) fi = fi / x * (x - 1);
	return fi;
}

int main() {
	int a, n;
	f >> a >> n;
	g << putere(a, fi(n) - 1, n) << '\n';
	return 0;
}