#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
__int128 _=1;int mo;
#define vi vector<int>
mt19937_64 rd(time(NULL)+37);
inline int rnd(int l,int r){;return rd()%(r-l+1)+l;}
inline int ksm(int x,int p,int mo,int y=1){for(;p;p/=2,x=_*x*x%mo)if(p&1)y=_*x*y%mo;return y;}
inline int pd(int a,int p){
	int r=0,k=p-1,l=p-1;
	for(;k&1^1;k>>=1)++r;
	for(a=ksm(a,k,p);r--&&a!=1;a=_*a*a%p)l=a;
	return a==1&&l+1==p;
}
inline int ip(int x){if(x<3)return x==2;f(i,1,40)if(!pd(rnd(2,x-1),x))return 0;return 1;}
inline int PR(int x){
    int a,b,c=rnd(1,x-1),d,e=127,s,t=0;
    for(a=1;a<=x;a<<=1){
        s=t;b=1;
    	f(r,1,a){
            t=(_*t*t+c)%x;
            if(s==t)return (d=__gcd(b,x))>1?d:PR(x); 
			b=_*b*abs(t-s)%x;
            if(!(r&e)&&(d=__gcd(b,x))>1)return d;
        }
        if((d=__gcd(b,x))>1)return d;
    }
    return PR(x); 
}
vi fj(int x){
	if(x<2)return{};
	if(ip(x))return{x};
	int p=PR(x),q=0;
	for(;x%p==0;x/=p)++q;
	vi a=fj(x),b=fj(p);
	f(_,1,q)for(int y:b)a.push_back(y);
	return a;
}
vi w;
int ask(int x){
	int z=m;
	for(int p:w)for(;z%p==0&&ksm(x,z/p,mo)==1;z/=p);
	return __gcd(x,mo)>1?1:z;
}
#define uq(a)sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end())
signed main(){
	cin>>m>>n;mo=m;
	w=fj(m);uq(w);
	for(int p:w)m=m/p*(p-1);
	w=fj(m);uq(w);
	s=1<<n;
	f(i,1,1e5)if((l=ask(i))%s==0){
		cout<<ksm(i,l/s,mo);exit(0);
	}
	cout<<-1;
	return 0;
}