#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[100000];
int1 di[10000],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 <= 100000 - 1; i++)
	{
		for( j = i + i ; j <= 100000 - 1; j += i )
			v[j] = 1;
	}
	for( i = 2; i<= 100000 - 1; 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 - 1  ;
	//fout<< fi <<'\n';
	fout << rid(A,  fi) % ret;



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