#include <fstream>
using namespace std;

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

int A, N, CN, phiN;
int i, bin[33], c;
long long d;

int main(){
	double phi;

	fin >> A >> N;
	phiN = N;
	CN = N;
	phi = phiN;
	for (i = 2; i <= CN; i++){
		if (!(CN%i)){
			phi *= i - 1;
			phi /= i;
			while (!(CN%i)) CN /= i;
		}
	}
	
	i = 0;
	phiN = int(phi) - 1;
	while (phiN) { bin[i++] = phiN % 2; phiN /= 2; }

	c = 0;
	d = 1;
	for (i = i - 1; i >= 0; i--){
		c = 2 * c;
		d = (d*d) % N;
		if (bin[i]){
			c++;
			d = (d*A) % N;
		}
	}

	fout << d;

	return 0;
}