#include <bits/stdc++.h>
using namespace std;
vector<long long> pr;
const long long mod = 1e9 + 7;
long long find(long long x) { return pr[x] = (pr[x] == x ? x : find(pr[x])); }
long long power(long long base, long long exp) {
  if (exp == 0) return 1;
  long long p = power(base, exp / 2);
  long long ans = (p * p) % mod;
  if (exp % 2 == 1) ans = (ans * base) % mod;
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long p, k, a, b, c;
  cin >> p >> k;
  if (k == 0) {
    cout << power(p, p - 1) << '\n';
    return 0;
  }
  if (k == 1) {
    cout << power(p, p) << '\n';
    return 0;
  }
  c = p - 1;
  pr.resize(p);
  iota(pr.begin(), pr.end(), 0);
  for (long long i = 1; i < p; i++) {
    a = i;
    b = (i * k) % p;
    if (b == 0) continue;
    if (find(a) != find(b)) {
      pr[find(a)] = find(b);
      c--;
    }
  }
  cout << power(p, c) << '\n';
  return 0;
}
