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

long long a, b, prod, i;

int main() {
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	scanf("%lld %lld", &a, &b);
	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;
}