#include <bits/stdc++.h>
const int maxn = 1e6 + 6;
int dsu[maxn], cnt[maxn];
void init() {
  for (int i = 0; i < maxn; i++) {
    dsu[i] = i;
    cnt[i] = 1;
  }
}
int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }
void Merge(int x, int y) {
  if (find(x) == find(y)) {
    return;
  }
  cnt[find(y)] += cnt[find(x)];
  dsu[find(x)] = find(y);
}
const int MOD = 1e9 + 7;
int qpow(int x, int k) {
  int res = 1;
  while (k > 0) {
    if (k & 1) {
      res = 1LL * res * x % MOD;
    }
    x = 1LL * x * x % MOD;
    k >>= 1;
  }
  return res;
}
int main() {
  int p, k;
  while (std::cin >> p >> k) {
    if (k == 1) {
      printf("%d\n", qpow(p, p));
      continue;
    }
    if (k == 0) {
      printf("%d\n", qpow(p, p - 1));
      continue;
    }
    init();
    for (int i = 1; i < p; i++) {
      Merge((1LL * k * i) % p, i);
    }
    int res = 0;
    for (int i = 1; i < p; i++) {
      if (find(i) == i) res++;
    }
    printf("%d\n", qpow(p, res));
  }
  return 0;
}
