#include<fstream>


using namespace std;

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

long long n , m ;

long long fi( long long x){
	
	long long count = x;
	
	for(long long i = 2 ; i*i <= x ; i++){
		if(x%i == 0){
			while(x%i == 0) x /= i;
			count = (count/i)*(i-1);
		}
	}
	
	if(x != 1) count = (count/x)*(x-1);
	
	return count;	
}

long long putere(long long a , long long b){
	
	long long p = a , sol = 1;
	
	while(b){
		
		if(b%2 == 1){
			sol *= p;
			sol %= m;
		}
		
		p *= p; p %= m;
		
		b /= 2;
	}
	return sol;
}

int main(){
	
	long long x;
	
	f>>n>>m;
	
	x = fi(m);
	
	g<<putere(n , x - 1);
	
	return 0;
}