#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#define debug_print(fmt, args...) printf(fmt, ##args)
#else
#define deb(fmt, args...)
#define debug_print(fmt, args...)
#endif
void print_array(vector<int> in, const string title = "Vector")
{
debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
for (unsigned int i = 0; i < in.size(); i++) {
debug_print("%d ", in[i]);
}
debug_print("\nDEBUG: ] END\n");
}
void print_matrix(vector<vector<int> > in, const string title = "Matrix")
{
debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
for (unsigned int i = 0; i < in.size(); i++) {
for (unsigned int j = 0; j < in[i].size(); j++) {
debug_print("%d ", in[i][j]);
}
debug_print("\nDEBUG: ");
}
debug_print("DEBUG: ] END\n");
}
void factors(int n, vector<int> &f)
{
f.clear();
for (int i = 2; i * i < n; i++) {
while (n % i == 0) {
f.push_back(i);
n /= i;
}
}
if (n > 1)
f.push_back(n);
}
ll exp(int a, int b, int mod)
{
if (b <= 0)
return 1;
if (b == 1)
return a;
if (b & 1) {
ll res = (a * exp(a, b - 1, mod)) % mod;
return res;
} else {
ll res = exp(a, b / 2, mod);
res = (res * res) % mod;
return res;
}
}
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
ll totient(int n, int m)
{
// vector<int> f;
ll res = 1;
for (int i = 2; i * i <= n; i++) {
int amount = 0;
while (n % i == 0) {
n /= i;
amount++;
}
if (amount > 0) {
res *= exp(i, amount - 1, m);
res *= (i - 1);
}
}
if (n > 1)
res *= (n - 1);
return res;
}
int main(int argc, char *argv[])
{
ios::sync_with_stdio(0);
cin.tie(0);
// Read the input parameters
int n, m;
cin >> n >> m;
if (gcd(n, m) != 1) {
cout << -1 << "\n";
return 0;
}
// x is the result of totient function
// deb("%lld\n", totient(n));
// deb("%lld\n", totient(m));
int tot = totient(m, m) - 1;
deb("n: %d, tot: %d\n", n, tot);
cout << exp(n, tot, m) % m << "\n";
return 0;
}
