#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int p, k, ver[1001000], po[1001000];
int main() {
  int i, r = 1;
  cin >> p >> k;
  if (k == 0) {
    for (i = 1; i < p; ++i) r = (1LL * r * p) % MOD;
    cout << r;
    return 0;
  }
  if (k == 1) {
    for (i = 0; i < p; ++i) r = (1LL * r * p) % MOD;
    cout << r;
    return 0;
  }
  po[0] = 1;
  for (i = 1; i <= 1000000; ++i) po[i] = (1LL * po[i - 1] * k) % p;
  for (i = 1; i < p; ++i)
    if (!ver[i]) {
      int j = i, l = 0;
      do {
        ver[j] = 1;
        ++l;
        j = (1LL * k * j) % p;
      } while (!ver[j]);
      if (po[l] == 1)
        r = (1LL * r * p) % MOD;
      else {
      }
    }
  cout << r;
  return 0;
}
