#include<bits/stdc++.h>

using namespace std;
#define ll long long 
ll a,m,b;

inline ll read(ll xs)
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-48;
		if(x>=m)f=1;
		x%=xs;
		ch=getchar();
	}
	return x+(f==1?xs:0);
}
ll phi(ll x)
{
	ll res=x;
 	for(ll i=2;i*i<=x;i++)
	{
		if(x%i)
		continue;
		res/=i;
		res*=(i-1);
		while(x%i==0)
		x/=i;
	}
	if(x>1)
	res/=x,res*=(x-1);
	return res;
}
ll qmi(ll x,ll k,ll mod)
{
	ll res=1;
	while(k)
	{
		if(k&1)
		res=res*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return res;
}
int main()
{
	scanf("%lld%lld",&a,&m);
	b=read(phi(m));
	printf("%lld",qmi(a,b,m));
	return 0;
}