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

long n, m, put;
long long val, rez;

long long phi(long num) {
	long aux = num;
	for (long i = 2; i * i <= num; ++i) {
		if( num % i == 0)
		{
			while (num % i == 0) num /= i;
			
			aux /= i;
			aux *= i-1;
			
		}
	}
	if( num != 1 )
		aux = (aux / num) * (num - 1);
	return aux;
}

int main() {
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	scanf("%ld %ld", &n, &m);
	
	put = phi(m) - 1; rez = 1; val = n;

	while (put) {
		if (put & 1) {
			rez *= 1LL * val;
			rez %= m * 1LL;
		}
		put >>= 1;
		val *= 1LL * val;
		val %= 1LL * m;
	}
	
	printf("%lld\n", rez);
	return 0;
}