#include<cstdio>
#include<vector>
#define ll long long

using namespace std;
ll n, a, k;
vector <bool> bit;
vector <int> prim;

void eratostene() {
	bit.assign(n + 1, 1);
	for(int i = 2; i <= n; i++)
		if(bit[i] == 1) {
			prim.push_back(i);
			for(int j = 2 * i; j <= n; j += i) bit[j] = 0;
		}
}

ll Pow(ll x, ll n) {
	if(n == 1) return x;
	if(n % 2 == 1) return x * Pow(x, n - 1);
	
	ll y = Pow(x, n / 2);
	return y * y;
}

ll cmmdc(ll a, ll b) {
	if(b == 0) return a;
	return cmmdc(b, a % b);
}

int main() {
	freopen("inversmodula.in", "r", stdin), freopen("inversmodular.out", "w", stdout);
	scanf("%lld %lld", &a, &n);

	eratostene();
	
	if(bit[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;
}