#include <fstream>
using namespace std;

long long put(long long a, long long p, long long mod)
{
	if (p == 0)
		return 1;
	long long n = put(a, p / 2, mod);
	n *= n;
	n %= mod;
	if (p & 1)
		n *= a;
	return (n % mod);
}

int main()
{
	int a, b, bp;
	ifstream in("inversmodular.in");
	ofstream out("inversmodular.out");
	in >> a >> b;
	bp = b;
	int phi = 1;
	for (int i = 2; i * i <= b; i++) {
		if (b % i == 0) {
			phi *= i - 1;
			b /= i;
			while (b % i == 0) {
				phi *= i;
				b /= i;
			}
		}
	}
	if (b != 1)
		phi *= b - 1;
	out << put(a, phi - 1, bp);
	return 0;
}