#include <bits/stdc++.h>

using namespace std;

int phi(int x) {
	int ans = x;

	for (int i = 2; i * i <= x; ++i) {
		if (x % i)
			continue;

		ans = (1LL * ans * (i - 1)) / i;

		while (x % i == 0)x /= i;
	}

	if (x > 1)
		ans = (1LL * ans * (x - 1)) / x;

	return ans;
}

int put(int a, int b, int mod) {
	int ans = 1;

	for (; b; b >>= 1) {
		if (b & 1)
			ans = 1LL * ans * a % mod;

		a = 1LL * a * a % mod;
	}

	return ans;
}
int main() {
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	int n, a;
	scanf("%d%d", &n, &a);
	printf("%d\n", put(a, phi(n) - 1, n));
}