#include <stdio.h>
#include <math.h>

long long a, b, prod, i, nr, n;

void div() {
	long h = 1;
	for (long i = 2; i * i <= n; ++i) {
		if (!(n % i)) {
			h *= i;
			while (n % i == 0) {
				n /= i;
			}
		}
	}
	nr /= h;
	nr /= n;
	nr *= (n - 1);
}

int main() {
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	scanf("%lld %lld", &a, &b);
	nr = a;
	n = a;
	div();
	a = nr;
	long long prod = 1;
	for (i = 0; ((long long)1 << i) <= (b - 2); ++i) {
		if (((1 << i) & (b - 2)) > 0) {
			prod = prod * a % b;	
		}
		a *= a; 
		a %= b;
	}
	printf("%lld\n", prod);
	return 0;
}