#include<fstream.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;
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 main()
{
	fin>>a>>n;
	int nr=0;
	int d,i;
	for(i=1;i<=n;i++)
	{
		d=euclid(i,n);
		if(d==1)
			nr++;
	}
	
	exponentiere(a,nr-1);
	return 0;
}