#include <bits/stdc++.h>
using namespace std;
int main() {
  long long p, k;
  cin >> p >> k;
  long sum = 1;
  if (k == 1) {
    sum = (sum * p) % (((long long)1e9) + 7);
  } else if (k == 0) {
    k = 1;
  }
  vector<int> t(p, true);
  t[0] = false;
  for (long long i = 1; i < p; ++i)
    if (t[i]) {
      sum = (sum * p) % (((long long)1e9) + 7);
      for (long long j = i; t[j]; j = (j * k) % p) t[j] = false;
    }
  cout << sum << endl;
}
