#include <bits/stdc++.h>
using namespace std;
long long MOD = 1000000007;
long long mod(long long a, long long p) {
  if (p == 0)
    return 1;
  else
    return a * mod(a, p - 1) % MOD;
}
int main() {
  long long p, k;
  cin >> p >> k;
  if (k == 0)
    cout << mod(p, p - 1);
  else if (k == 1)
    cout << mod(p, p);
  else {
    long long m = 1, ano = k;
    for (; ano != 1; m++) ano = ano * k % p;
    cout << mod(p, (p - 1) / m) << endl;
  }
  return 0;
}
