#include <bits/stdc++.h>
using namespace std;
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
const int INF = 1 << 29;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n >> b) & 1; }
inline void set_bit(int& n, int b) { n |= two(b); }
inline void unset_bit(int& n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) {
  int res = 0;
  while (n && ++res) n -= n & (-n);
  return res;
}
template <class T>
void chmax(T& a, const T& b) {
  a = max(a, b);
}
template <class T>
void chmin(T& a, const T& b) {
  a = min(a, b);
}
int main() {
  long long p, k, ans;
  cin >> p >> k;
  if (k == 0) {
    ans = 1;
    for (long long i = 1; i < p; i++) {
      ans *= p;
      ans %= 1000000007;
    }
  } else if (k == 1) {
    ans = 1;
    for (long long i = 1; i <= p; i++) {
      ans *= p;
      ans %= 1000000007;
    }
  } else {
    ans = 1;
    long long ord;
    long long k_a = k;
    for (ord = 1; k_a != 1;) {
      k_a *= k;
      k_a %= p;
      ord++;
    }
    for (long long i = 1; i <= (p - 1) / ord; i++) {
      ans *= p;
      ans %= 1000000007;
    }
  }
  cout << ans << endl;
}
