#include <bits/stdc++.h>
long long mo = 1e9 + 7;
long long qpow(long long a, long long b, long long p) {
  long long res = 1, Pow = b;
  while (b) {
    if (b & 1) res = res * Pow % p;
    Pow = Pow * Pow % p;
    b >>= 1;
  }
  return res;
}
bool used[1000005];
int main() {
  int p, k;
  long long ans = 1;
  scanf("%d%d", &p, &k);
  if (k == 1) return !printf("%lld", qpow(p - 1, p, mo));
  for (int i = 1; i <= p - 1; i++) {
    if (used[i]) continue;
    long long x = i;
    while (!used[x]) {
      used[x] = true;
      x = x * k % p;
    }
    ans = ans * p % mo;
  }
  printf("%lld", ans);
}
