#include <bits/stdc++.h>
using namespace std;
bool gotCycle[1000006];
int k, p, i, conv[1000006], cycle[1000006], MOD = 1000000007, tempLength, x,
                                            contributing[1000006];
long long ans;
set<int> eligible;
set<int>::iterator it, jt;
int BigMod(int b, int idx) {
  if (idx == 0) return 1;
  int ret = BigMod(b, idx / 2);
  ret = (((long long)ret) * ((long long)ret)) % MOD;
  if (idx & 1) ret = (((long long)ret) * ((long long)b)) % MOD;
  return ret;
}
int main() {
  cin >> p >> k;
  if (k == 0) {
    cout << BigMod(p, p - 1) << endl;
    return 0;
  }
  if (k == 1) {
    cout << BigMod(p, p) << endl;
    return 0;
  }
  for (i = 0; i <= p; i++) {
    cycle[i] = 0;
    gotCycle[i] = false;
  }
  for (i = 0; i < p; i++) conv[i] = (((long long)i) * ((long long)k)) % p;
  for (i = 0; i < p; i++) {
    if (gotCycle[i]) continue;
    gotCycle[i] = true;
    tempLength = 1;
    x = conv[i];
    while (!gotCycle[x]) {
      gotCycle[x] = true;
      x = conv[x];
      tempLength++;
    }
    cycle[tempLength]++;
  }
  for (i = 1; i <= p; i++)
    if (cycle[i] != 0) eligible.insert(i);
  assert(eligible.size() == 2);
  for (it = eligible.begin(); it != eligible.end(); it++) contributing[*it] = 0;
  for (it = eligible.begin(); it != eligible.end(); it++)
    for (jt = eligible.begin(); jt != eligible.end(); jt++)
      if ((*jt) >= (*it) && (*jt) % (*it) == 0)
        contributing[*jt] = (((long long)contributing[*jt]) +
                             ((long long)cycle[(*it)]) * ((long long)(*it))) %
                            MOD;
  ans = 1;
  for (it = eligible.begin(); it != eligible.end(); it++) {
    ans = ans * BigMod(contributing[*it], cycle[*it]);
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}
