#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int p, k, par[N], size[N], c[N];
int getp(int u) {
  if (u == par[u]) return u;
  return par[u] = getp(par[u]);
}
void merge(long long u, long long v) {
  u = getp(u), v = getp(v);
  if (u == v) return;
  if (u > v) swap(u, v);
  par[v] = min(u, v);
  size[u] += size[v];
}
int main() {
  int i;
  cin >> p >> k;
  for (i = 0; i < p; ++i) par[i] = i, size[i] = 1;
  for (i = 0; i < p; ++i) {
    long long next = (1LL * k) * i;
    assert(next >= 0);
    next %= p;
    merge(i, next);
  }
  for (i = 0; i < p; ++i)
    if (par[i] == i) c[size[i]]++;
  long long ret = 1, x, basic = c[1];
  for (i = 0; i < p; ++i)
    if (par[i] == i) {
      if (size[i] == 1)
        ret = (ret * basic) % mod;
      else {
        x = c[size[i]];
        x = (x * size[i]) % mod;
        ret = (ret * (basic + x)) % mod;
      }
    }
  if (k == 0) {
    ret = 1;
    for (i = 0; i < p - 1; ++i) ret = (ret * p) % mod;
  }
  cout << ret << endl;
}
