#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void Read(T &x) {
  int f = 1;
  char t = getchar();
  while (t < '0' || t > '9') {
    if (t == '-') f = -1;
    t = getchar();
  }
  x = 0;
  while (t >= '0' && t <= '9') {
    x = x * 10 + t - '0';
    t = getchar();
  }
  x *= f;
}
const int modulo = 1000000007;
const int maxn = 1000005;
int p, k;
int fst[maxn], v[maxn << 1], nxt[maxn << 1], e_cn;
bool flag[maxn], vis[maxn], cycle;
void addedge(int x, int y) {
  e_cn++;
  v[e_cn] = y, nxt[e_cn] = fst[x], fst[x] = e_cn;
}
void input() { Read(p), Read(k); }
int pwr(long long x, long long k) {
  long long re = 1;
  while (k > 0) {
    if (k & 1) re = 1ll * re * x % modulo;
    x = 1ll * x * x % modulo;
    k >>= 1;
  }
  return re;
}
void dfs(int cn) {
  vis[cn] = true;
  cycle |= flag[cn];
  for (register int i = fst[cn]; i; i = nxt[i]) {
    if (!vis[v[i]]) {
      dfs(v[i]);
    }
  }
}
void solve() {
  if (k == 0) {
    cout << pwr(p, p - 1) << endl;
    return;
  }
  if (k == 1) {
    cout << pwr(p, p) << endl;
    return;
  }
  long long ans = 1;
  for (register int i = 0; i < p; i++) {
    int x = i, y = 1ll * i * k % p;
    if (x == y)
      flag[x] = true;
    else
      addedge(x, y), addedge(y, x);
  }
  for (register int i = 0; i < p; i++) {
    if (!vis[i]) {
      cycle = false;
      dfs(i);
      if (!cycle) ans = 1ll * ans * p % modulo;
    }
  }
  cout << ans << endl;
}
int main() {
  input();
  solve();
  return 0;
}
