#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long)1e18;
const int mod = (int)1e9 + 7;
const int MAXN = (int)2e6 + 5;
long long p;
long long bp(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b % 2) res = (res * a) % mod;
    a = (a * a) % mod;
    b = b / 2;
  }
  return res;
}
bool done[MAXN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long k;
  cin >> p >> k;
  if (k == 0) {
    cout << bp(p, p - 1) << '\n';
  } else if (k == 1) {
    cout << bp(p, p) << '\n';
  } else {
    long long ans = 0;
    for (int i = 1; i < p; i++) {
      if (done[i]) continue;
      done[i] = 1;
      ans++;
      long long cur = i;
      cur = i * k % p;
      while (cur != i) {
        done[cur] = 1;
        cur = cur * k % p;
      }
    }
    cout << bp(p, ans) << '\n';
  }
}
