#include<stdio.h>
long long n,m;
long long phi(long long nr){
	long long a=nr;
	for(long long i=2;i*i<=nr;++i){
		if(nr%i==0){
			while(nr%i==0)
				nr/=i;
			a=(a/i)*(i-1);
		}
	}
	if(nr!=1)
		a=(a/nr)*(nr-1);
	return a;
}
int main(){
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	long long put,p,congr=1,nr;
	scanf("%lld%lld",&n,&m);
	
	put=phi(m)-1;
	nr=n;
	for(p=1;p<=put;p<<=1){
		if(p & put)
			congr=(congr*nr)%m;
		nr=(nr*nr)%m;
	}
	printf("%lld\n",congr);
	fclose(stdin);
	fclose(stdout);
	return 0;
}