#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
  long long p, k;
  cin >> p >> k;
  vector<bool> seen(p);
  long long ans = 1;
  for (int i = (k != 1); i < p; i++) {
    if (seen[i]) continue;
    for (int j = i; !seen[j]; j = (k * j) % p) {
      seen[j] = true;
    }
    ans = (ans * p) % MOD;
  }
  cout << ans << '\n';
}
