#include <bits/stdc++.h>
using namespace std;
int binPow(long long b, int p, int M) {
  long long res = 1;
  while (p) {
    if (p & 1) res = res * b % M;
    b = b * b % M;
    p >>= 1;
  }
  return res;
}
const int MOD = 1e9 + 7, mxN = 1e6;
long long p, k, ans = 1;
bool vis[mxN];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> p >> k;
  if (k == 0) {
    cout << binPow(p, p - 1, MOD) << '\n';
    return 0;
  }
  for (int i = 0; i < p; ++i) {
    if (vis[i]) continue;
    int cnt = 0;
    long long u = i;
    while (!vis[u]) {
      vis[u] = 1;
      ++cnt;
      u = u * k % p;
    }
    if (binPow(k, cnt, p) == 1) ans = ans * p % MOD;
  }
  cout << ans;
  return 0;
}
