#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long p, k;
long long l = 1, k_c;
int main() {
  cin >> p >> k;
  k_c = (k * k) % p;
  while (k_c != k) {
    ++l;
    k_c = (k_c * k) % p;
  }
  long long res = 1;
  for (int i = 1; i <= (p - 1) / l; ++i) {
    res = (res * p) % mod;
  }
  if (k == 1) {
    res = (res * p) % mod;
  }
  cout << res;
  return 0;
}
