#include <fstream>

using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
//const int modu=1000000007;
long long putere_log (long long a,long long n,long long modulol)
{
	if(n==0)
		return 1;
	else
	{
		if(n%2==1)
			return ((a%modulol)*((putere_log((a%modulol)*(a%modulol)%modulol,n/2,modulol)%modulol)))%modulol;
		else
			return (putere_log(((a%modulol)*(a%modulol))%modulol,n/2,modulol))%modulol;
	}
}
long long phi_de_n (long long n)
{
	long long phin=1,d=2,contorcrt;
	while(n>1)
	{
		if(n%d==0)
		{
			contorcrt=0;
			while(n%d==0)
				n/=d,contorcrt++;
			phin=phin*(d-1)*putere_log(d,contorcrt-1,1000000007);
		}
		d++;
		if(d*d>n)
			d=n;
	}
	return phin;
}
long long invers_modular(long long a,long long n)
{
	//n=phi_de_n(n);
	return putere_log(a,phi_de_n(n)-1,n);
	
}
int main ()
{
	long long a,n;
	fin>>a>>n;
	fout<<invers_modular(a,n);
	return 0;
}