#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
using vll = vector<LL>;
using LD = long double;
template <typename T>
void check(T& a, const T& b) {
  if (a >= b) {
    a %= b;
  }
}
template <typename T>
T gcd(T u, T v) {
  if (u == v) return u;
  if (u == 0) return v;
  if (v == 0) return u;
  if (~u & 1) {
    if (v & 1)
      return gcd(u >> 1, v);
    else
      return gcd(u >> 1, v >> 1) << 1;
  }
  if (~v & 1) return gcd(u, v >> 1);
  if (u > v) return gcd((u - v) >> 1, v);
  return gcd((v - u) >> 1, u);
}
LL mulmod(LL a, LL b, const LL& m) {
  LL q = (LL)(((LD)a * (LD)b) / (LD)m);
  LL r = a * b - q * m;
  if (r > m) r %= m;
  if (r < 0) r += m;
  return r;
}
template <typename T, typename S>
T expo(T e, S n) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = x * p;
    p = p * p;
    n >>= 1;
  }
  return x;
}
template <typename T>
T powerL(T e, T n, const T& m) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = mulmod(x, p, m);
    p = mulmod(p, p, m);
    n >>= 1;
  }
  return x;
}
const int N = (int)1e6 + 10;
const int MOD = (int)1e9 + 7;
int k, p, vis[N];
vector<vi> g;
void dfs(int u) {
  vis[u] = true;
  for (int& i : g[u]) {
    if (!vis[i]) dfs(i);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cerr.tie(NULL);
  ;
  cin >> p >> k;
  g.resize(p + 1);
  for (int i = 0; i < p; i++) {
    LL x = (i * 1LL * k) % p;
    g[i].push_back(x);
  }
  int ans = (k == 1 ? p : 1);
  for (int i = 1; i <= p - 1; i++) {
    if (!vis[i]) {
      dfs(i);
      ans = (ans * 1LL * p) % MOD;
    }
  }
  cout << ans << '\n';
  return 0;
}
