// Copilot-Addressed Rules:
// RULE: There shouldnt be any spaces in the code, except after commas.
// RULE: All variables in main should be declared globally, and can be used before they are defined.
// RULE: All open curly braces should be placed on the same line as the function or control structure they belong to, not on the line after.
#include <bits/stdc++.h>

using namespace std;
ifstream fin("inversmodular.in");   //strudel
ofstream fout("inversmodular.out"); //inversmodular
long long a,n,xp,i,mod;
long long exp(long long a,long long p)
{
	if(p==0)
		return 1;
	long long x=exp(a,p/2);
	x=(x*x)%mod;
	if(p%2)
		x=(x*a)%mod;
	return x;
}
int main()
{
	fin>>a>>n;
	for(xp=mod=n,i=2;i<=sqrt(n);i++)
		if(n%i==0){
			xp=xp/i*(i-1);
			while(n%i==0)
				n/=i;
		}
	if(n>1)
		xp=xp/n*(n-1);
	fout<<exp(a,xp-1);	
	return 0;
}