#include <fstream> 
#include <deque>
#include <vector>
#include <string>
#include <cmath>
#include <climits>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stack>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
long long phi(long long n) {
	long long d = 2;
	long long ans = n;
	long long sum = 1;
	while (n > 1) {
		bool intra = false;
		while (n % d == 0) {
			n /= d;
			intra = true;
		}
		if (intra) {
			sum *= d;
			ans *= (d - 1);
		}
		d++;
	}
	return ans / sum;;
}
long long power(long long a, long long b, long long p) {
	if (b == 0) {
		return 1;
	}
	if (b % 2 == 1) {
		return (a * power(a, b - 1, p)) % p;
	}
	long long P = power(a, b / 2, p);
	return (P * P) % p;
}
int main() {
	long long a, mod;
	cin >> a >> mod;
	cout << power(a, phi(mod) - 1, mod);
}