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

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

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

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