#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 6;
int mod = 1e9 + 7;
int pw[N];
bool usd[N];
int q[N];
int main() {
  int p, k;
  cin >> p >> k;
  pw[0] = 1;
  for (int i = 1; i <= p; ++i) pw[i] = (1ll * pw[i - 1] * p) % mod;
  if (k == 0) {
    cout << pw[p - 1] << endl;
    return 0;
  }
  if (k == 1) {
    cout << pw[p] << endl;
    return 0;
  }
  for (int i = 1; i < p; ++i) {
    if (!usd[i]) {
      usd[i] = 1;
      int len = 1, m = (1ll * i * k) % p;
      for (; !usd[m]; ++len, m = (1ll * m * k) % p) usd[m] = 1;
      q[len]++;
    }
  }
  int ans = 1;
  for (int i = 1; i < p; ++i) {
    for (int j = 0; j < q[i]; ++j) ans = (1ll * ans * pw[1]) % mod;
  }
  cout << ans << endl;
  return 0;
}
