#include <bits/stdc++.h>
using namespace std;
void RI() {}
template <typename... T>
void RI(int& head, T&... tail) {
  scanf("%d", &head);
  RI(tail...);
}
const long long MOD = 1e9 + 7;
long long myPow(int base, int p) {
  if (p == 1) return base;
  long long t = myPow(base, p / 2);
  if (p & 1)
    return t * t % MOD * base % MOD;
  else
    return t * t % MOD;
}
int main() {
  int p, k;
  RI(p, k);
  if (k == 0)
    cout << myPow(p, p - 1) << endl;
  else if (k == 1)
    cout << myPow(p, p) << endl;
  else {
    int x = 1, ord = 0;
    do {
      x = (long long)x * k % p;
      ord++;
    } while (x != 1);
    cout << myPow(p, (p - 1) / ord) << endl;
  }
  return 0;
}
