#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
inline istream& operator>>(istream& fin, pair<T1, T2>& pr) {
  fin >> pr.first >> pr.second;
  return fin;
}
template <class T0, class T1, class T2>
inline istream& operator>>(istream& fin, tuple<T0, T1, T2>& t) {
  fin >> get<0>(t) >> get<1>(t) >> get<2>(t);
  return fin;
}
template <class T>
inline istream& operator>>(istream& fin, vector<T>& a) {
  for (auto& u : a) fin >> u;
  return fin;
}
template <class T, size_t n>
inline istream& operator>>(istream& fin, array<T, n>& a) {
  for (auto& u : a) fin >> u;
  return fin;
}
template <class FwdIter>
inline auto dump(FwdIter first, FwdIter last, const char* dlm) -> void {
  copy(first, last,
       ostream_iterator<typename iterator_traits<FwdIter>::value_type>(cout,
                                                                       dlm));
}
inline int64_t powmod(int64_t a, int64_t n, const int64_t mod) {
  if (a == 1 || !n) return mod != 1 ? 1 : 0;
  int64_t out = 1;
  for (; n; n >>= 1) {
    if (n & 1) out = out * a % mod;
    a = a * a % mod;
  }
  return out;
}
int64_t probB() {
  const int64_t mod = 1000000007;
  int64_t p, k;
  cin >> p >> k;
  if (k == 0) {
    return powmod(p, p - 1, mod);
  }
  vector<bool> tag(p, false);
  int64_t out = k == 1 ? p : 1;
  for (int64_t i = 1; i < p; ++i)
    if (!tag[i]) {
      out = (out * p) % mod;
      for (auto j = i; !tag[j]; j = (j * k) % p) tag[j] = true;
    }
  return out;
}
int main(const int argc, char* argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << probB();
  return EXIT_SUCCESS;
}
