#include<fstream>
#define int1 long long
#define nmax 2000000000
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int1 N , A, i, j, k, ret;
//bool v[100000];
//int  a[50000];
int1 di[1000],p;
int1 rid( int1 A, int1 fi )
{
	int1 t;
	if(fi == 1)
		return A % ret ;
	if(fi % 2 == 0)
	{
		t = rid(A, fi/2) % ret;
		return t * t % ret;
	}
	else
		return rid(A, fi-1) % ret  * A %ret;
}
void read()
{
	int1 s = 0, semn = 1, sp =0, fi;
	fin >> A >> N;
	ret = N;
//	for( i = 2; i <= N; i++)
//	{
//		for( j = i + i ; j <= A; j += i )
//			v[j] = 1;
//	}
//	for( i = 2; i<= N; i++)
//	{
//		if(!v[i])
//			a[++k] = i;
//
//	}
//	k = 1 ;
//	while(N>1)
//	{
//		if(N % a[k] == 0)
//		{
//			di[++p] = a[k];
//			while(N % a[k] == 0)
//			{
//				N /= a[k];
//			}
//
//		}
//		k++;
//
//	}
//	for( i = 1; i< 1<<p ; i++ )
//	{
//		semn = -1;
//		sp = 0;
//		for( j = 0 ; j < p; j++)
//		{
//			if(i & 1<< j)
//			{
//				semn *= (-1);
//				sp += ret / di[j+1] ;
//
//			}
//		}
//		s += sp * semn;
//	}
//	fi = ret - s   ;
//	//fout<< fi <<'\n';
	fout << rid(A,  ret -2) % ret;



}
int main()
{
	read();
	fin.close();
	fout.close();
	return 0;
}