#include <bits/stdc++.h>
using namespace std;
bool VIS[1000006];
long long k, p;
long long MOD = 1000000007;
void dfs(long long x) {
  if (VIS[x]) return;
  VIS[x] = 1;
  dfs(k * x % p);
}
long long Pow(long long x, long long t) {
  long long res = 1;
  while (t) {
    if (t & 1) res = res * x % MOD;
    t >>= 1;
    x = x * x % MOD;
  }
  return res % MOD;
}
int main() {
  cin.sync_with_stdio(false);
  cin >> p >> k;
  if (k == 1) {
    cout << Pow(p, p) << endl;
    return 0;
  }
  if (k == 0) {
    cout << Pow(p, p - 1) << endl;
    return 0;
  }
  long long anss = 0;
  for (int i = 1; i < p; i++) {
    if (VIS[i]) continue;
    anss++;
    dfs(i);
  }
  cout << Pow(p, anss) << endl;
  return 0;
}
