#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const long long INF = 1e9 + 19;
const int MOD = 1e9 + 7;
int n, k;
bool use[N];
void read() { cin >> n >> k; }
void solve() {
  int mod = n;
  int cnt = 0;
  for (int i = 1; i < n; i++) {
    if (!use[i]) {
      int v = i;
      for (; !use[v];) {
        use[v] = 1;
        v = v * 1ll * k % mod;
      }
      cnt++;
    }
  }
  if (k == 1) cnt++;
  long long answer = 1;
  for (int i = 0; i < cnt; i++) answer = (answer * n) % MOD;
  cout << answer << endl;
}
void printAns() {}
void stress() {}
int main() {
  if (1) {
    int k = 1;
    for (int tt = 0; tt < k; tt++) {
      read();
      solve();
      printAns();
    }
  } else {
    stress();
  }
  return 0;
}
