# include <bits/stdc++.h>
using namespace std;
using ll=long long;
using lll=__int128;
constexpr int prime[8]={2,3,5,7,11,13,61,24251};
mt19937_64 rnd;
template<typename T>
inline void clear(T &x){T().swap(x);}
ll power(ll a,ll b,ll c)
{
	ll ans=1;
	for(;b;b>>=1,a=(lll)a*a%c)
		if(b&1) ans=(lll)ans*a%c;
	return ans;
}
bool MR(ll a,ll n)
{
	if(a%n==0 || power(a,n-1,n)!=1) return true;
	ll t=n-1,m=0;
	while(!(t&1)) t>>=1,m++;
	ll x=power(a,t,n);
	for(int i=0;i<m;i++)
	{
		ll y=(lll)x*x%n;
		if(y==1 && x!=1 && x!=n-1) return true;
		x=y;
	}
	return x!=1;
}
bool ispri(ll n)
{
	if(n==1) return false;
	for(int i=0;i<8;i++)
		if(n==prime[i]) return true;
		else if(MR(prime[i],n)) return false;
	return true;
}
ll PR(ll n)
{
	ll x=rnd()%(n-1)+1,c=rnd()%(n-1)+1,y=x,s=1;
	for(ll i=1,j=2,g;;i++)
	{
		x=((lll)x*x+c)%n;s=(lll)s*abs(x-y)%n;
		if(!s) return n;
		if(i==j)
		{
			if((g=__gcd(s,n))>1) return g;
			y=x;j<<=1;
		}
	}
}
void slv(ll n,vector<ll> &vec)
{
	if(n==1) return;
	if(ispri(n)) return vec.push_back(n),void();
	ll x;
	while((x=PR(n))>=n);
	slv(x,vec);slv(n/x,vec);
}
int main()
{
	int K;
	ll n,w=1;
	vector<ll> d;
	cin>>n>>K;
	slv(n,d);
	sort(d.begin(),d.end());
	d.resize(unique(d.begin(),d.end())-d.begin());
	ll phi=n;
	for(ll i:d) phi=phi/i*(i-1);
	if(phi%(1<<K) || (phi==(1<<K) && (n%8==0 || d.size()>2 || (n%4==0 && d.size()>1)))) return puts("-1"),0;
	clear(d);slv(phi,d);
	auto ord=[&](ll w)
	{
		ll ans=phi;
		for(ll i:d)
			while(ans%i==0 && power(w,ans/i,n)==1)
				ans/=i;
		return ans;
	};
	ll m=1<<K-1;
	for(ll i:d) if(i>2) m*=i;
	while(__gcd(w,m)>1 || power(w,m,n)==1) w++;
	cout<<power(w,ord(w)>>K,n)<<endl;
	return 0;
}