#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
bool used[MAXN];
int cnt[MAXN];
int to[MAXN];
const int MOD = 1e9 + 7;
int main() {
  int p, k;
  cin >> p >> k;
  for (int i = 0; i < p; ++i) {
    if (!used[i]) {
      int len = 0;
      for (long long j = i; !used[j]; j = (k * j) % p) {
        ++len;
        assert(len <= p);
        used[j] = true;
      }
      ++cnt[len];
    }
  }
  for (int i = 1; i <= p; ++i) {
    for (int j = i; j <= p; j += i) {
      assert(cnt[i] * i <= p);
      to[j] += i * cnt[i];
      assert(to[j] <= p);
    }
  }
  long long ans = 1;
  if (k == 0) {
    for (int i = 1; i < p; ++i) {
      ans = (ans * p) % MOD;
    }
  } else {
    for (int i = 1; i <= p; ++i) {
      for (int j = 0; j < cnt[i]; ++j) {
        ans = (ans * to[i]) % MOD;
      }
    }
  }
  cout << ans << '\n';
}
