#include <bits/stdc++.h>
 
using namespace std;

int lgput(int a, int b, int mod) {
	int ret = 1;
	while(b) {
		if(b&1) ret = 1ll*ret*a%mod;
		a = 1ll*a*a%mod;
		b>>=1;
	}

	return ret;
}
int main() {
	#ifdef BLAT
		freopen("input", "r", stdin);
	#else
		freopen("inversmodular.in", "r", stdin);
		freopen("inversmodular.out", "w", stdout);
	#endif
 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int a, n;
	cin >> a >> n;

	int phi = n;
	int cop = n;
	if(cop % 2 == 0){
		phi /= 2;
		while(cop % 2 == 0) cop >>= 1;
	}

	int d = 3;
	while(d*d <= cop) {
		if(cop % d == 0)  {
			phi /= d;
			phi *= d-1;
		}
		while(cop % d == 0) {
			cop /= d;
		}
		d += 2;
	}

	if(cop != 1) {
		phi /= cop;
		phi *= cop-1;
	}

	cout << lgput(a, phi - 1, n) << '\n';
	return 0;
}