#include <bits/stdc++.h>
const int mod = 1000000007;
struct modn {
  int n;
  modn() {}
  modn(long long x) { n = (x >= 0 ? x % mod : (x % mod + mod) % mod); }
  modn& operator-() {
    n = mod - n;
    return *this;
  }
  void print() const { printf("%d\n", n); }
};
bool operator==(const modn& A, const modn& B) { return A.n == B.n; }
bool operator!=(const modn& A, const modn& B) { return A.n != B.n; }
modn operator+(const modn& A, const modn& B) { return A.n + B.n; }
modn operator-(const modn& A, const modn& B) { return A.n - B.n; }
modn operator*(const modn& A, const modn& B) { return (long long)A.n * B.n; }
modn pow_mod(const modn& A, long long x) {
  modn s = 1, t = A;
  for (; x; x >>= 1) {
    if (x & 1) s = s * t;
    t = t * t;
  }
  return s;
}
modn operator/(const modn& A, const modn& B) { return A * pow_mod(B, mod - 2); }
const int maxn = 1000010;
bool vis[maxn];
int p, k;
void solve() {
  scanf("%d%d", &p, &k);
  modn res = 1;
  if (k == 0) {
    for (int i = 0; i < p - 1; ++i) res = res * p;
    res.print();
    return;
  }
  if (k == 1) {
    for (int i = 0; i < p; ++i) res = res * p;
    res.print();
    return;
  }
  memset(vis, 0, sizeof vis);
  for (int i = 0; i < p; ++i)
    if (!vis[i]) {
      int csz = 0;
      int q = i;
      while (!vis[q]) {
        vis[q] = 1;
        ++csz;
        q = ((long long)k * q) % p;
      }
      if (csz > 1) res = res * p;
    }
  res.print();
}
int main() {
  solve();
  return 0;
}
