#include <bits/stdc++.h>
using namespace std;
const long long Mod = 1000000007LL;
long long fp(long long a, long long k) {
  long long res = 1LL;
  while (k) {
    if (k & 1) res = res * a % Mod;
    a = a * a % Mod;
    k >>= 1;
  }
  return res;
}
int main() {
  int p, k;
  scanf("%d%d", &p, &k);
  if (k == 0)
    printf("%I64d\n", fp(p, p - 1));
  else if (k == 1)
    printf("%I64d\n", fp(p, p));
  else {
    int r = 0;
    long long now = 1LL;
    for (r = 1; r <= p; r++) {
      now = now * k % p;
      if (now == 1) break;
    }
    printf("%I64d\n", fp(p, (p - 1) / r));
  }
  return 0;
}
