#include<fstream>
#define nmax 2000000000
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int N , A, i, j, k, ret;
bool v[1000001];
int a[200000];
int di[1000],p;
int rid( int A, int fi )
{
	int 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 ;
}
void read()
{
	int 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 -1  ; 
	//fout<< fi <<'\n'; 
	fout << rid(A,  fi - 1);
	
	
		
}
int main()
{
	read();
	fin.close();
	fout.close();
	return 0;
}