#include <fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

bool prim(int n){
	if(n < 2) return 0;
	if(n == 2) return 1;
	if(n % 2 == 0) return 0;
	for(int i = 3; i*i <= n; i += 2){
		if(n % i == 0){
			return 0;
		}
	}
	return 1;
}

int put(int b, int exp, int mod){
	int ans = 1;
	while(exp){
		if(exp % 2 == 0){
			exp /= 2;
			b = 1LL*b*b % mod;
		}
		else {
			ans = 1LL*ans * b% mod;
			--exp;
		}
	}
	return ans;
}

int fi(int n){
	int ans = n;
	int auxn = n;
	if(auxn % 2 == 0){
		ans /= 2;
		while(auxn % 2 == 0) auxn /= 2;
	}
	int d = 3;
	while(d*d <= auxn){
		if(auxn % d == 0){
			ans /= d;
			ans *= d - 1;
			while(auxn % d == 0) auxn /= d;
		}
		d += 2;
	}
	ans /= auxn;
	if(auxn != 1) ans *= auxn - 1;
	return ans;
}


int main()
{
	int a, n;
	fin >> a >> n;
	fout << put(a, fi(n)-1, n);
	return 0;
}