#include <bits/stdc++.h>
using namespace std;
int n, p, r[1000005], a[1000005];
int mul(int a, int b) {
  int res = 1;
  for (long long i = a; b > 0; i = (i * i) % 1000000007) {
    if (b % 2) res = (i * res) % 1000000007;
    b /= 2;
  }
  return res;
}
int findset(int u) {
  if (r[u] == 0) return u;
  return (r[u] = findset(r[u]));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> p;
  for (int x = 1; x < n; ++x) {
    int y = 1ll * x * p % n;
    int rx = findset(x);
    int ry = findset(y);
    if (rx == ry) continue;
    r[rx] = ry;
  }
  int dem = 0;
  for (int i = 1; i < n; ++i) {
    int x = findset(i);
    if (a[x]) continue;
    a[x]++;
    dem++;
  }
  if (p == 1) dem++;
  cout << mul(n, dem);
  return 0;
}
