#include <bits/stdc++.h>
long long N,A;
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long Phi(long long n)
{
	long long c=n;
	for(long long i=2;i*i<=n;++i)
	{
		if (n%i==0)
		{
			while(n%i==0) n/=i;
			c=(c/i)*(i-1);
		}
	}
    if(n!=1) c=c/n*(n-1);
	return c;
}

int main()
{
	fin>>A>>N;
    long long p=Phi(N)-1;
	long long n=A;
	long long c=1;
    for(long long i=1;i<=p;i<<=1)
    {
	 	if(i&p)c=(c*n)%N;
	  	n=(n*n)%N;
	}
	fout<<c;
	return 0;
}