#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unordered_map<int, int> iiMap;
ll ModPow(ll base, ll ex, ll mod) {
if (ex == 0) return 1 % mod;
ll tmp = ModPow(base, ex/2, mod);
tmp = (tmp * tmp) % mod;
if (ex % 2 == 1) tmp = (tmp * base) % mod;
return tmp;
}
iiMap factors(ll val) {
iiMap fac; // fac: count
for (int x = 2; x*x <= val; x++) {
while (val%x == 0) {
if (!fac.count(x)) {
fac[x] = 0;
}
fac[x]++;
val /= x;
}
}
if (val > 1) {
if (!fac.count(val)) {
fac[val] = 0;
}
fac[val]++;
}
return fac;
}
ll phi(ll val) {
if (val < 1) return 0;
iiMap facs = factors(val);
ll total = 1;
for (auto kv: facs) {
total *= powl(kv.first, kv.second - 1) * (kv.first - 1);
}
return total;
}
ll ModInv(ll val, ll mod) {
ll pm = phi(mod);
return ModPow(val, pm - 1, mod);
}
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a%b);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
ll a, m;
cin >> a >> m;
if (a == 0 || gcd(a, m) != 1) {
cout << "-1\n";
return 0;
}
cout << ModInv(a, m) << "\n";
return 0;
}