#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long my_pow(long long x, long long n) {
  long long ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    x %= mod;
    ret %= mod;
    n >>= 1;
  }
  return ret;
}
int main() {
  long long p, k;
  scanf("%lld %lld", &p, &k);
  long long ans = 0;
  if (k == 0ll) {
    ans = my_pow(p, p - 1);
  } else if (k == 1) {
    ans = my_pow(p, p);
  } else {
    int ord = 1;
    long long cur = k;
    while (cur != 1) {
      cur = (cur * k) % p;
      ord++;
    }
    ans = my_pow(p, (p - 1) / ord);
  }
  printf("%lld", ans);
  return 0;
}
