#include <bits/stdc++.h>
using namespace std;
int k, p;
const long long mod = 1e9 + 7;
long long pow1(long long x, long long n) {
  long long ret = 1;
  long long num = x;
  while (n) {
    if (n & 1) {
      ret *= num;
      ret %= mod;
    }
    num *= num;
    num %= mod;
    n >>= 1;
  }
  return ret;
}
int main() {
  while (~scanf("%d%d", &p, &k)) {
    int m = 1;
    long long temp = k;
    if (k == 0) {
      printf("%lld\n", pow1(p, p - 1));
      continue;
    }
    if (k == 1) {
      printf("%lld\n", pow1(p, p));
      continue;
    }
    for (; m < p; m++) {
      if (temp == 1) break;
      temp *= k;
      temp %= p;
    }
    int x = ceil((p - 1) * 1.0 / m);
    printf("%lld\n", pow1(p, x));
  }
}
