#include <bits/stdc++.h>
using namespace std;
long long mod = 1e9 + 7;
long long p, k;
long long po(long long x, long long n, long long mo) {
  long long res = 1;
  while (n) {
    if (n % 2) {
      res = (res * x) % mo;
      --n;
    } else {
      x = (x * x) % mo;
      n /= 2;
    }
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> p >> k;
  if (k == 0) {
    cout << po(p, p - 1, mod);
    return 0;
  }
  if (k == 1) {
    cout << po(p, p, mod);
    return 0;
  }
  int m = 1;
  while (po(k, m, p) != 1) ++m;
  cout << po(p, (p - 1) / m, mod);
  return 0;
}
