#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
inline long long mod(long long a, long long m) { return (a % m + m) % m; }
long long inverse(long long a, long long m) {
  if ((a = mod(a, m)) == 1) return 1;
  return mod((1 - m * inverse(m % a, a)) / a, m);
}
long long pow_mod(long long a, long long k, long long m) {
  if (k == 0) return 1;
  long long t = pow_mod(a, k / 2, m);
  return mod(mod(t * t, m) * (k % 2 ? a : 1), m);
}
int main() {
  long long P, K;
  while (cin >> P >> K) {
    long long ans;
    if (K == 0) {
      ans = pow_mod(P, P - 1, MOD);
    } else {
      long long x = 1, c = 0;
      do {
        ++c;
        (x *= K) %= P;
      } while (x != 1);
      assert((P - 1) % c == 0);
      long long t = (P - 1) / c;
      ans = pow_mod(P, t, MOD);
      if (K == 1) (ans *= P) %= MOD;
    }
    cout << ans << endl;
  }
}
