#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const long long P = 1000000007LL;
const int maxN = 1100000;
int k, p;
bool used[maxN];
int main() {
  scanf("%d%d", &p, &k);
  if (k == 0) {
    long long res = 1;
    for (int i = 1; i < p; ++i) {
      res = (res * p) % P;
    }
    printf("%d\n", (int)(res));
    return 0;
  }
  long long res = 1;
  for (int i = 1; i < p; ++i) {
    if (used[i]) {
      continue;
    }
    res = (res * p) % P;
    int j = i;
    while (!used[j]) {
      used[j] = true;
      j = ((long long)(j) * (long long)(k)) % (long long)(p);
    }
  }
  if (k == 1) {
    res = (res * p) % P;
  }
  printf("%d\n", (int)(res));
  return 0;
}
