#include <bits/stdc++.h>
typedef long long ll;
typedef __int128 lll;
using namespace std;
mt19937_64 rng(time(0));
const int N=11048550;
int K,pr[729510],p=0;
bool isnt[N+10];
ll n,m,np,ny;
int na=0;
void init(){
	for(int i=2;i<=N;i++){
		if(!isnt[i]) pr[++p]=i;
		for(int j=1;j<=p&&pr[j]*i<=N;j++){
			isnt[pr[j]*i]=1;
			if(i%pr[j]==0) break;
		}
	}
}
ll ksm(ll a,ll k){
	ll res=1;
	for(;k;k>>=1,a=a*a) if(k&1) res=res*a;
	return res; 
}
ll ksm(ll a,ll k,ll p){
	ll res=1;
	for(;k;k>>=1,a=lll(a)*a%p) if(k&1) res=lll(res)*a%p;
	return res;
}
void t_r_y(ll p,ll phi){
	if(na) return;
	for(;(double)clock()/CLOCKS_PER_SEC<1.0&&!na;){
		ll y=ksm(rng()%p,phi>>K,p),nw=1;
		bool fl=1;
		for(int j=1;j<(1<<K);j++){
			nw=lll(nw)*y%p;
			if(nw<=1){
				fl=0;
				break;
			}
		}
		nw=lll(nw)*y%p;
		if(nw!=1) fl=0;
		if(fl){
			np=p,na=1,ny=y;
			break;
		}
	}
}
void chk(ll p,int a){
	if(na) return;
	if(p==2){
		if(a-1-(a>=3)>=K) t_r_y(ksm(p,a),ksm(p,a-1-(a>=3)));
		return;
	}
	if((p-1)&((1<<K)-1)) return;
	t_r_y(ksm(p,a),(p-1)*ksm(p,a-1));
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b) return x=1,y=0,a;
	ll t=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return t;
}
ll mul(ll a,ll b,ll m){
	ll res=0;
	for(;b;b>>=1,a=2*a%m) if(b&1) res=(res+a)%m;
	return res;
}
void exCRT(ll &M,ll &R,ll m,ll r){
	ll x,y,g=exgcd(M,m,x,y),c=(r-R%m+m)%m;
	if(c%g) exit(1);
	x=mul(x,c/g,m/g);
	R+=x*M;
	M*=(m/g);
	R=(R%M+M)%M;
}
int main(){
	init();
	scanf("%lld%d",&n,&K),m=n;
	for(int i=1;i<=p;i++) if(m%pr[i]==0){
		int c=0;
		while(m%pr[i]==0) c++,m/=pr[i];
		chk(pr[i],c);
	}
	for(int j=1;j<=N;j++){
		ll nw=(((ll)j)<<K)+1;
		int c=0;
		while(m%nw==0) c++,m/=nw;
		if(c) chk(nw,c);
	}
	chk(m,1);
	if(!na) puts("-1");
	else{
		exCRT(np,ny,n/np,1%(n/np));
		printf("%lld\n",ny);
	}
}