#include <bits/stdc++.h>
using namespace std;
long long powr(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b % 2 == 1) res = res * a % 1000000007;
    a = a * a % 1000000007;
    b /= 2;
  }
  return res;
}
int main() {
  int p, k;
  cin >> p >> k;
  vector<int> g[p];
  bool x[p];
  memset(x, false, sizeof x);
  vector<set<long long>> a;
  if (k == 0) {
    long long ans = powr(p, p - 1);
    cout << ans << '\n';
    return 0;
  }
  for (int i = 0; i < p; ++i) {
    if (x[i]) continue;
    x[i] = 1;
    long long yy = i;
    set<long long> xz;
    xz.insert(i);
    do {
      yy *= k;
      yy %= p;
      x[yy] = 1;
      xz.insert(yy);
    } while (yy != i);
    a.push_back(xz);
  }
  long long ans = 1;
  ans = powr(p, a.size() - 1);
  if (k == 1) {
    ans *= p;
    ans %= 1000000007;
  }
  cout << ans << '\n';
}
