#include <bits/stdc++.h>
using namespace std;
void solve(istream &in, ostream &out);
int main() {
  ios::sync_with_stdio(false);
  solve(cin, cout);
  return 0;
}
void solve(istream &in, ostream &out) {
  long long const mod = 1000LL * 1000LL * 1000LL + 7LL;
  long long p, k;
  in >> p >> k;
  vector<char> t(p);
  long long counter = 0;
  for (long long i = 1; i < p; ++i) {
    if (!t[i]) {
      ++counter;
      long long j = i;
      while (!t[j]) {
        t[j] = true;
        j = (j * k) % p;
      }
    }
  }
  if (k == 1) {
    ++counter;
  }
  long long res = 1;
  for (long long i = 0; i < counter; ++i) {
    res = (res * p) % mod;
  }
  out << res << endl;
}
