#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;
inline int fpow(int a, int st, int mod) {
  int ans = 1;
  while (st) {
    if (st % 2) ans = (long long)ans * a % mod;
    a = (long long)a * a % mod;
    st /= 2;
  }
  return ans;
}
int a, b, c, d, n, m, k, p, inv;
bool used[1000002];
inline void mark(int s) {
  int v = s;
  while (!used[v]) {
    used[v] = 1;
    v = (long long)v * k % p;
  }
  v = s;
  used[v] = 0;
  while (!used[v]) {
    used[v] = 1;
    v = (long long)v * inv % p;
  }
}
int main() {
  scanf("%d%d", &p, &k);
  if (k == 0) {
    printf("%d\n", fpow(p, p - 1, 1000000007));
    exit(0);
  }
  int ans = 1;
  if (k == 1) {
    ans = p;
  }
  inv = fpow(k, p - 2, p);
  for (int _n((p - 1)), i(1); i <= _n; i++) {
    if (!used[i]) {
      ans = (long long)ans * p % 1000000007;
      mark(i);
    }
  }
  printf("%d\n", ans);
}
