#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
template <ll P>
struct mod_t {
  ll x;
  mod_t() : x(0) {}
  mod_t(ll in) : x(in % P) {}
  mod_t operator+(const mod_t& rhs) { return (ll(x) + ll(rhs.x)) % P; }
  mod_t operator*(const mod_t& rhs) { return (ll(x) * ll(rhs.x)) % P; }
};
const ll P = 1e9 + 7;
using mod = mod_t<P>;
mod fexp(mod a, ll e) {
  mod ans(1);
  for (; e; e /= 2ll, a = a * a)
    if (e % 2ll) ans = ans * a;
  return ans;
}
void traverse(vector<ll>& A, ll k, ll i) {
  ll p = A.size();
  for (ll j = i; A[j] != i; j = (k * j) % p) A[j] = i;
}
int main() {
  ll p, k;
  cin >> p >> k;
  if (k == 0) cout << fexp(p, p - 1).x << endl;
  if (k == 1) cout << fexp(p, p).x << endl;
  if (k <= 1) return 0;
  int cnt = 0;
  vector<ll> A(p);
  for (int i = 1; i < p; i++)
    if (A[i] == 0) cnt++, traverse(A, k, i);
  cout << fexp(p, cnt).x << endl;
}
