#include <bits/stdc++.h>
using namespace std;
const long long Mo = 1000000007LL;
long long p, k, m, now;
long long ksm(long long a, long long b) {
  if (!a) return 0;
  long long ans = 1LL;
  for (; b; b >>= 1) {
    if (b & 1) ans *= a, ans %= Mo;
    a *= a;
    a %= Mo;
  }
  return ans;
}
int main() {
  cin >> p >> k;
  if (k == 0)
    cout << ksm(p, p - 1) << endl;
  else if (k == 1)
    cout << ksm(p, p) << endl;
  else {
    k %= p;
    m = 1;
    now = k;
    while (now != 1) m++, now *= k, now %= p;
    cout << ksm(p, (p - 1) / m) << endl;
  }
  return 0;
}
