#include <cstdio>
using namespace std;
typedef long long ll;
ll A, N, P;

ll DET(ll k) {
	ll nr = k, i;
	for(i = 2; i * i <= k; ++i)  {
		if(k % i == 0) {
			while(k % i == 0) k /= i;
			nr = (nr / i) * (i - 1);
		}
	}

	if(k > 1)
		nr = (nr / k) * (k - 1);
	return nr;
}

int main() {
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	scanf("%lld %lld", &A, &N);
	P = DET(N) - 1;
//	printf("%lld\n", P);
	ll i , inv = 1, a = A;
	for(i = 1; i <= P; i *= 2) {
		if((i & P) > 0) inv = (inv * a) % N;
			a = (a * a) % N;
		}

	printf("%lld \n", inv);

	return 0;
}