#include <fstream>
using namespace std;
ifstream f("inversmodular.in"); ofstream g("inversmodular.out");
#define ll long long
ll A, N, MOD, sol;
ll compute(ll p){
	if (p == 0) return 1;
	ll x = compute(p/2);
	x = (x * x) % MOD;
	if (p % 2) x = (x * A) % MOD;
	return x;		
}
int main(){
	f>>A>>N;MOD=N;N=N-2;
	sol=compute(N);g<<sol<<'\n'; g.close();
	return 0;
}