#include <bits/stdc++.h>
using namespace std;
const int MOD(1000000007);
const int INF((1 << 30) - 1);
const int MAXN(1000005);
int par[MAXN], chk[MAXN];
int findhead(int u) { return u == par[u] ? u : par[u] = findhead(par[u]); }
long long power(long long x, int n) {
  if (n == 0) return 1ll;
  long long ret = power(x, n / 2);
  ret = (ret * ret) % MOD;
  if (n & 1) ret = (ret * x) % MOD;
  return ret;
}
int main() {
  long long p, k;
  cin >> p >> k;
  if (k == 0) {
    cout << power(p, p - 1);
    return 0;
  }
  if (k == 1) {
    cout << power(p, p);
    return 0;
  }
  for (int i = 1; i <= p - 1; i++) par[i] = i;
  for (int i = 1; i <= p - 1; i++) {
    long long x = k * i % p;
    par[findhead(i)] = findhead(x);
  }
  int cnt = 0;
  for (int i = 1; i <= p - 1; i++) {
    int x = findhead(i);
    if (!chk[x]) {
      cnt++;
      chk[x] = 1;
    }
  }
  cout << power(p, cnt);
}
