#include <bits/stdc++.h>
using namespace std;
int p, k;
int powy(int x, int y) {
  if (!y) return 1;
  int z = powy(x, y / 2);
  z = (1LL * z * z) % 1000000007;
  if (y % 2) {
    z = (1LL * z * x) % 1000000007;
  }
  return z;
}
int main() {
  std::ios_base::sync_with_stdio(false);
  cin >> p >> k;
  if (k == 0) {
    cout << powy(p, p - 1);
    return 0;
  }
  if (k == 1) {
    cout << powy(p, p);
    return 0;
  }
  int d = 0;
  int x = 1;
  for (d = 1; d < p; ++d) {
    x = (1LL * x * k) % p;
    if (x == 1) break;
  }
  cout << powy(p, (p - 1) / d);
  return 0;
}
