#include <bits/stdc++.h>
using namespace std;
const int SZ = 1.1e6;
const long long M = 1e9 + 7;
bool used[SZ];
int main() {
  long long p, k, res = 1;
  cin >> p >> k;
  if (k == 0) {
    for (int i = 1; i < p; i++) res = (res * p) % M;
    cout << res;
    return 0;
  }
  for (int i = 0; i < p; i++) {
    if (used[i]) continue;
    used[i] = true;
    for (long long a = (k * i) % p; a != i; a = (k * a) % p) used[a] = true;
    if (k == 1) res = (res * p) % M;
    if (k > 1 && i != 0) res = (res * p) % M;
  }
  cout << res;
}
