#include<fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

long long a, n, vprim[50000], lprim, lacat, aux, chestie;
bool vciur[50000];

void eratos()
{
	for(int i = 2; i<=50000; i++)
	{
		if(vciur[i]==0)
		{
			vprim[lprim] = i;
			lprim++;

			if(i<300)
			for(int j = i * i; j<=50000; j+=i)
				vciur[j] = 1;
		}
	}
}

long long alab(long long a, long long b)
{
	long long p = 1, ad = a;

	while(b!=0)
	{
		if(b%2==1)
			p *= ad;

		ad *= ad;
		b /= 2;

		ad %= n;
		p %= n;
	}

	return p;
}



int main(){
	int player_unu=0;
	eratos();

	in>>a>>n;
	lacat = aux = n;
	while(aux!=1 && chestie<lprim)
	{
		if(aux%vprim[chestie]==0)
		{
			lacat = lacat * (vprim[chestie] - 1) / vprim[chestie];

			while(aux%vprim[chestie]==0)
				aux /= vprim[chestie];
		}

		chestie++;
	}

	if(aux!=1)
		lacat = lacat * (aux - 1) / aux;

	lacat--;

	out<<alab(a, lacat)<<'\n';
	return player_unu;
}