#include <bits/stdc++.h>
#pragma warning(disable : 4996)
using namespace std;
const int mod = 1e9 + 7;
long long p, k;
long long po(long long x, long long k) {
  long long n = 1;
  while (k > 0) {
    if (k & 1) n = (n * x) % mod;
    x = (x * x) % mod;
    k = k >> 1;
  }
  return n;
}
int main() {
  cin >> p >> k;
  if (k == 0) {
    cout << po(p, p - 1) << endl;
  } else if (k == 1) {
    cout << po(p, p) << endl;
  } else {
    int i;
    long long res = 1;
    for (i = 1;; i++) {
      res = res * k;
      if (res % p == 1) break;
      res = res % p;
    }
    cout << po(p, (p - 1) / i) << endl;
  }
  return 0;
}
