#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1}, dy[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int p, k;
int powmod(int x, int e, int m) {
  if (e == 0) return 1ll % m;
  if (e & 1) return 1ll * x * powmod(x, e - 1, m) % m;
  return powmod(1ll * x * x % m, e / 2, m);
}
bool vis[1000100];
vector<int> adj[1001000];
int dfs(int i) {
  if (vis[i]) return 0;
  vis[i] = 1;
  int res = 1;
  for (auto y : adj[i]) res += dfs(y);
  return res;
}
int main() {
  cin >> p >> k;
  if (k == 0) {
    cout << powmod(p, p - 1, 1e9 + 7) << endl;
    return 0;
  }
  int ki = powmod(k, p - 2, p);
  for (int i = 0; i < p; ++i) {
    adj[i].push_back((1ll * i * ki) % p);
  }
  int multi = 0;
  for (int i = 0; i < p; ++i) {
    int c = dfs(i);
    if (c == 0) continue;
    if (powmod(k, c, p) == 1) multi++;
  }
  cout << powmod(p, multi, 1e9 + 7) << endl;
}
