#include <cstdio>

#define file_in "inversmodular.in"
#define file_out "inversmodular.out"

long long A,N;

long long put(long long A, long long B, long long mod){
	
	if (B==0)
		return 1;
	if (B%2==0){
		long long X=put(A,B/2,mod);
		return ((X%mod)*(X%mod))%mod;
	}
	else{
		long long X=put(A,B/2,mod);
		return ((((X%mod)*(X%mod))%mod)*(A%mod))%mod;
	}
}

long long euler(long long X){
	long long XX=X;
	int d;
	for (d=2;d*d<=X;++d){
		
		if (X%d==0){
			while(X%d==0)
			 X/=d;
		    XX=(XX/d)*(d-1);
		}
	}
	
	if (X>1)
		XX=(XX/X)*(X-1);
	
	return XX;
}

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%lld %lld", &A, &N);
	
	long long phi=euler(N)-1;
	
	printf("%lld\n", put(A,phi,N));
	
	return 0;
}