#include <bits/stdc++.h>
int main() {
  int p, k, i, j, r;
  scanf("%d%d", &p, &k);
  j = 1;
  for (i = 1; i <= p - 1; i++) {
    j = (long long)j * k % p;
    if (j == 1) break;
  }
  if (k == 0) i = 1;
  r = 1;
  for (j = 0; j < (p - 1) / i; j++) r = (long long)r * p % 1000000007;
  if (k == 1) r = (long long)r * p % 1000000007;
  printf("%d", r);
  return 0;
}
