#include <cstdio>

int A, N;

int totient(int N) {
	int result = N;
	for (int i = 2; i * i <= N; i++) {
		if (N % i == 0) {
			result = result / i * (i - 1);
			while (N % i == 0) {
				N /= i;
			}
		}
	}

	if (N != 1) {
		result = result / N * (N - 1);
	}

	return result;
}

int lgput(int base, int exponent, int MOD) {
	int result = 1, basePowTwo = base;
	for (int bit = 0; (1 << bit) <= exponent; bit++) {
		if (exponent & (1 << bit)) {
			result = (1LL * result * basePowTwo) % MOD;
		}
		basePowTwo = (1LL * basePowTwo * basePowTwo) % MOD;
	}

	return result;
}

int main() {
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);

	scanf("%d%d", &A, &N);
	printf("%d\n", lgput(A, totient(N) - 1, N));
	return 0;
}