#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1000 * 1000 + 5, Mod = 1000 * 1000 * 1000 + 7;
long long p, k, tul[Maxn], ans = 1;
bool mark[Maxn];
int powee(int a, int b) {
  long long jav = 1;
  for (int i = 0; i < b; i++) {
    jav *= (long long)a;
    jav %= Mod;
  }
  return jav;
}
int dfs(int v) {
  mark[v] = true;
  long long a = ((long long)v * (long long)k) % p;
  if (!mark[a]) return dfs(a) + 1;
  return 1;
}
void dfsAll() {
  for (int i = 0; i < p; i++)
    if (!mark[i]) tul[dfs(i)]++;
  return;
}
int main() {
  cin >> p >> k;
  if (k == 0) {
    cout << powee(p, p - 1) << endl;
    return 0;
  }
  dfsAll();
  long long a;
  for (int i = 2; i < p; i++) {
    a = ((long long)i * (long long)tul[i] + 1) % Mod;
    ans *= (long long)powee(a, tul[i]);
    ans %= Mod;
  }
  ans *= (long long)powee(tul[1], tul[1]);
  ans %= Mod;
  cout << ans << endl;
  return 0;
}
