#include <iostream>
#include <algorithm>
#include <chrono>
#include <random>
#include <vector>
using ll=long long;
std::mt19937_64 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
using L=__int128;
ll fp(ll a,ll b,ll c){ll ans=1,off=a;while(b){if(b&1) ans=(L)ans*off%c;off=(L)off*off%c;b>>=1;}return ans;}
constexpr ll tn[]={2,325,9375,28178,450775,9780504,1795265022};
bool check(ll a,ll p)
{
	ll d(p-1),w(fp(a,d,p));
	if(w!=1) return 1;
	while((d&1)^1)
	{
		if((w=fp(a,(d>>=1),p))==p-1) return 0;
		else if(w!=1) return 1;
	}
	return 0;
}
bool miller_rabin(ll a)
{
	for(ll c:tn) if(a==c) return a==2;
	for(ll c:tn)
	{
		ll b(c%a);
		if(b==0) continue;
		if(check(b,a)) return false;
	}
	return true;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll pollard_rho(ll x)
{
	ll s=0,t=0,c=1LL*rnd()%(x-1)+1,j=0,k=1,tmp=1;
	for(k=1;;k<<=1,s=t,tmp=1)
	{
		for(j=1;j<=k;++j)
		{
			t=(L(t)*t+c)%x;
			tmp=(L)tmp*std::abs(t-s)%x;
			if((j%127)==0)
			{
				ll d=gcd(tmp,x);
				if(d>1) return d;
			}
		}
		ll d=gcd(tmp,x);
		if(d>1) return d;
	}
	return 1;
}
void fact(ll n,std::vector<ll> &ps)
{
	if(n<2) return;
	if(miller_rabin(n)){ps.emplace_back(n);return;}
	ll p=n;
	while(p>=n) p=pollard_rho(n);
	while((n%p)==0) n/=p;
	fact(n,ps),fact(p,ps);
}
bool check(ll m,const std::vector<ll> &ps)
{
	if(m%2) return ps.size()==1;
	else return ((m/2)%2)==1 && ps.size()==2;
}
int main()
{
	ll m;int k;
	std::cin>>m>>k;std::vector<ll> ps;fact(m,ps);
	ll phi(m);std::sort(ps.begin(),ps.end());ps.resize(std::unique(ps.begin(),ps.end())-ps.begin());
	for(ll v:ps) phi=phi/v*(v-1);
	if(phi%(1<<k))
	{
		std::cout<<"-1\n";
		return 0;
	}
	if(phi==(1<<k))
	{
		if(!check(m,ps))
		{
			std::cout<<"-1\n";
			return 0;
		}
	}
	ps.clear();fact(phi,ps);
	ll t(phi),q(1);while((t%2)==0) t/=2,q*=2;
	ll t0(t*(1<<(k-1)));
	ll w(1);
	// std::cout<<phi<<" "<<t<<std::endl;
	while(fp(w,t0,m)==1 || gcd(w,m)!=1) ++w;
	// std::cout<<w<<" "<<fp(w,t0,m)<<"\n";
	w=fp(w,t,m);
	// std::cout<<fp(w,q,m)<<std::endl;
	while(fp(w,(1<<k),m)!=1) w=L(w)*w%m;
	std::cout<<w<<std::endl;
	return 0;
}