/*#include<fstream.h>
#include<assert.h>
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
const int n_max=10001;//definim numarul maxim de cifre al numerelor
const int m=1;
long long a,n;
int nr=0;
int prim(int x)
{
	int d,sw;
	
	sw=1;d=2;
	while(d<=x/2 && sw)
	{
	if(x%d==0)
	sw=0;
	d++;	
	}
	if(sw) 
		return 1;
	else 
		return 0;

}
void exponentiere(long long a, long long p)
{
	unsigned int i;
	long long sol=1;
	for(i=0;(1<<i)<=p;i++)	// luam toti biti lui p la rand
	{
		if(((1<<i)&p)>0)// daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
			sol=(sol*a)%n;
		a=(a*a)%n;// inmultim a cu a ca sa obtinem n^(2^i+1);
	}
	fout<<sol<<'\n';
}
int euclid(int a,int b)
{
	
	if(b==0)
		return a;
	else
		return euclid(b,a%b);
}
int numarare()
{
	
	int i=1;
	assert(1<=i && i<=n);
	if(euclid(i,n)!=0)
		return ++nr;
	else
		return (euclid(i+1,n));
	
}
int main()
{
	fin>>a>>n;
	
	if(a+1==n)
	{
		fout<<a<<'\n';
		return 0;
	}
	if(prim(n)==1)
	{
		exponentiere(a,n-2);
		return 0;
	}
	numarare();
	//fout<<nr<<'\n';
	int nr=0;
	int d,i=1;
	while(i<=n)
	{
		d=euclid(i,n);
		if(d==1)
			nr++;
		i++;
	}
		exponentiere(a,nr-1);
	return 0;
}*/
#include<stdio.h>
#define LL long long


LL N,M;

LL getphi(LL nr)
{
	LL cur = nr;
	for(LL i = 2;i * i <= nr; ++i)
	{
		if (nr % i == 0)
		{
			while(nr % i == 0)nr /= i;
			cur = (cur / i) * (i - 1);
		}
	}
        if (nr != 1) cur = cur / nr * (nr - 1);
	return cur;
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld %lld\n",&N,&M);
        LL put = getphi(M) - 1;
	LL nr = N;
	LL crt = 1;
    for(LL p = 1;p <= put;p <<= 1)
    {
	 	if (p & put) crt = (crt * nr) % M;
	  	nr = (nr * nr) % M;
	}
	printf("%lld\n",crt);
	return 0;
}