#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long power(long long a, long long p) {
  long long ans = 1;
  while (p) {
    if (p & 1LL) {
      ans *= a;
      ans %= mod;
    }
    p /= 2;
    a *= a;
    a %= mod;
  }
  return ans;
}
int main() {
  int p, k;
  cin >> p >> k;
  if (k == 0) {
    cout << power(p, p - 1) << endl;
    return 0;
  }
  map<int, int> group;
  vector<int> seen(p, 0);
  seen[0] = 1;
  for (int i = 1; i < p; i++) {
    if (!seen[i]) {
      long long c = i;
      int len = 0;
      while (!seen[c]) {
        seen[c] = 1;
        c = (c * k) % p;
        len++;
      }
      group[len]++;
    }
  }
  long long res = 1;
  for (const auto& g : group) {
    res *= power(g.first * g.second + 1, g.second) % mod;
    res %= mod;
  }
  if (group[1] != 0) {
    res *= (group[1] + 1);
    res %= mod;
  }
  cout << res << endl;
  return 0;
}
