#include <bits/stdc++.h>
using namespace std;
const int mmod = 1000000007;
int pw(int a, int b) {
  if (b == 0) return 1;
  int c = pw(a, b / 2);
  c = (1LL * c * c) % mmod;
  if (b % 2) c = (1LL * a * c) % mmod;
  return c;
}
int main() {
  int p, k;
  cin >> p >> k;
  if (k == 0) {
    cout << pw(p, p - 1) << endl;
    return 0;
  }
  if (k == 1) {
    cout << pw(p, p) << endl;
    return 0;
  }
  vector<int> used(p);
  int up = 0;
  for (int i = 1; i < p; i++) {
    if (used[i]) continue;
    int j = i;
    while (!used[j]) {
      used[j] = 1;
      j = (1LL * j * k) % p;
    }
    up++;
  }
  cout << pw(p, up) << endl;
}
