#include<cstdio>
#define ll long long

using namespace std;
ll n, a, k;

bool prim(ll x) {
	if(x <= 1 || x % 2 == 0) return false;
	if(x == 2) return true;
	
	for(int i = 3; i * i <= x; i += 2)
		if(x % i == 0) return false;
	
	return true;
}

ll Pow(ll x, ll n) {
	ll p = 1;
	
	while(n > 0) {
		if(n % 2 == 1) { p = p * x; n--; }
		x = x * x, n /= 2;
	}
	
	return p;
}

ll cmmdc(ll a, ll b) {
	ll c;
	
	while(b) {
		c = a % b;
		a /= b;
		b = c;
	}
	
	return a;
}

int main() {
	freopen("inversmodula.in", "r", stdin), freopen("inversmodular.out", "w", stdout);
	scanf("%lld %lld", &a, &n);
	
	if(prim(n)) k = n - 2;
	else {
		for(int i = 2; i < n; i++)
			if(cmmdc(i, n) == 1) k++;
	}
	
	printf("%lld\n", Pow(a, k) % n);
	
	return 0;
}