#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
const double EPS = 1e-8;
const double PI = acos(-1.0);
const long long MOD = 1e9 + 7;
void run() {
  long long k, p;
  int d;
  scanf("%I64d", &p);
  scanf("%I64d", &k);
  if (k == 0)
    d = p - 1;
  else if (k == 1)
    d = p;
  else {
    int s = 1;
    for (long long m = k; m != 1; m = (m * k) % p, ++s)
      ;
    d = (p - 1) / s;
  }
  long long ans = 1;
  for (int i = 0; i < d; ++i) ans = (ans * p) % MOD;
  printf(
      "%I64d"
      "\n",
      ans);
}
int main() {
  run();
  return 0;
}
