#include <fstream>
#define ll long long

int n, k;

int prod(int a, int b) { return (1ll*a*b)%k; }

int putlog(int n, int k) {
	if(k==0) return 1;
	int x = putlog(n, k/2);
	if(k%2==0) return prod(x, x);
	return prod(n, prod(x, x));
}

int calcphi(int n) {
	ll ans = n;
	for(int i=2;i*i<=n;i++)
		if(!(n%i)){
			while(!(n%i)) n/=i;
			ans = ans/i*(i-1);
		}
	if(n!=1) ans = ans/n*(n-1);
	return ans;
}

int main() {
	std::ifstream fin("inversmodular.in");
	std::ofstream fout("inversmodular.out");
	fin>>n>>k;
	int phi = calcphi(k);
	fout<<putlog(n, phi-1);
}