#include <bits/stdc++.h>
using namespace std;
int p, k, cnt;
bool used[1000005];
int main() {
  cin >> p >> k;
  if (k == 1) {
    cnt = p;
    goto fail;
  }
  for (int i = 1; i < p; i++) {
    if (used[i]) continue;
    cnt++;
    long long j = i;
    while (!used[j]) {
      used[j] = 1;
      j *= 1LL * k;
      j %= p;
    }
  }
fail:;
  long long ret = 1;
  for (int i = 0; i < cnt; i++) ret = ret * 1LL * p % 1000000007LL;
  cout << ret << endl;
}
