#include<fstream>
#include<cmath>

#define LL long long

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

LL lgput(LL a, LL n);

LL n3;

int main(){
	LL a,n,phi,i,x,n2;
	
	f>>a>>n;
	
	n2=sqrt(n)+1;
	phi=n;
	n3=n;
		
	for(i=2; i<= n2; ++i){
		if(!(n%i)){
			phi=phi-phi/i;
			n/=i;
			while(!(n%i))
				n/=i;
		}
	}
	if(n>1){
		phi=phi-phi/n;
	}
	
	phi--;
	
	g<<lgput(a,phi);
	
	f.close();
	g.close();
return 0;
}

LL lgput(LL a, LL n){
	if(n==1){
		return a%n3;
		
	}	
	else
		if(n%2) {
			long long t;
			a%=n3;
			t=(a*a)%n3;
			return a*(lgput(t,(n-1)/2))%n3;
		}
		else{
			long long t;
			a%=n3;
			t=(a*a)%n3;
			return lgput(t,n/2);
		}
}