#include <bits/stdc++.h>
using namespace std;
// debug
template<class T> ostream& operator<<(ostream&, const vector<T>&);
template<class T> ostream& operator<<(ostream&, const set<T>&);
template<class T> ostream& operator<<(ostream&, const multiset<T>&);
template<class K, class V> ostream& operator<<(ostream&, const map<K, V>&);
template<class T, size_t N> ostream& operator<<(ostream&, const array<T, N>&);
template<class A, class B> ostream& operator<<(ostream& os, const pair<A, B>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<class T>
void print_collection(ostream& os, const T& v) {
os << "{";
bool first = true;
for (const auto& x : v) {
if (!first) os << ", ";
first = false;
os << x;
}
os << "}";
}
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { print_collection(os, v); return os; }
template<class T> ostream& operator<<(ostream& os, const set<T>& v) { print_collection(os, v); return os; }
template<class T> ostream& operator<<(ostream& os, const multiset<T>& v) { print_collection(os, v); return os; }
template<class K, class V> ostream& operator<<(ostream& os, const map<K, V>& v) { print_collection(os, v); return os; }
template<class T, size_t N> ostream& operator<<(ostream& os, const array<T, N>& v) { print_collection(os, v); return os; }
#define dbg(x) cerr << #x << " = " << (x) << '\n'
using ll = long long;
constexpr int INF = 1'000'000'000; // 1e9
constexpr ll LINF = 1'000'000'000'000'000'000LL; // 1e18
constexpr int MOD = 1'000'000'007; // 1e9 + 7
inline ll add(ll a, ll b) { return (a + b) % MOD; }
inline ll sub(ll a, ll b) { return ((a - b) % MOD + MOD) % MOD; }
inline ll mul(ll a, ll b) { return (a * b) % MOD; }
int modpow(int x, int n, int m) {
if (n == 0) return 1%m;
ll u = modpow(x,n/2,m);
u = (u*u)%m;
if (n%2 == 1) u = (u*x)%m;
return u;
}
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a%b);
}
int eulerTotient(int n) {
ll result = n;
for (ll p = 2; p <= n / p; p++) {
if (n % p == 0) {
while (n % p == 0)
n /= p;
result -= result / p;
}
}
if (n > 1)
result -= result / n;
return result;
}
void solve() {
int a, m;
cin >> a >> m;
a %= m;
if (gcd(a, m) != 1) {
cout << -1;
return;
}
cout << modpow(a, eulerTotient(m)-1, m);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}