#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)
{
// vector<pair<int, int>> f;
f.clear();
for (int i = 2; i * i < n; i++) {
// int sum = 0;
while (n % i == 0) {
// sum++;
f.push_back(i);
n /= i;
}
// if (sum > 0) {
// f.push_back({i, sum});
// }
}
if (n > 1)
f.push_back(n);
}
ll count(int a, int b)
{
int mod = 1000000007;
if (b == 0)
return 1;
if (b == 1)
return a;
if (b & 1) {
deb("pariton %d\n", b);
ll res = (a * count(a, b - 1)) % mod;
return res;
} else {
ll res = count(a, b / 2);
res = (res * res) % mod;
return res;
}
}
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
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;
}
vector<int> f;
factors(n, f);
sort(f.begin(), f.end());
int num = f[0];
int amount = 0;
ll x = 1;
for (unsigned int i = 0; i < f.size(); i++) {
if (f[i] == num) {
amount++;
continue;
} else {
x *= count(num, amount - 1);
x *= num - 1;
num = f[i];
amount = 0;
}
}
x *= count(num, amount - 1);
x *= num - 1;
cout << x << "\n";
return 0;
}
