#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, N = 1e6 + 5, MOD = 1e9 + 7;
int T, cas = 0;
bool vis[N];
long long p, k;
long long quick_mod(long long a, long long b, long long m) {
  long long ret = 1;
  a %= m;
  while (b > 0) {
    if (b & 1) ret = ret * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return ret;
}
int main() {
  cin >> p >> k;
  if (k == 0) {
    cout << quick_mod(p, p - 1, MOD) << endl;
    return 0;
  }
  if (k == 1) {
    cout << quick_mod(p, p, MOD) << endl;
    return 0;
  }
  memset(vis, false, sizeof(vis));
  long long ans = 1;
  int cnt = 0;
  for (int i = 0; i < p; i++) {
    int idx = i, flag = 0;
    while (!vis[idx]) {
      vis[idx] = 1;
      flag++;
      idx = 1LL * idx * k % p;
    }
    cnt += flag > 1;
  }
  cout << quick_mod(p, cnt, MOD) << endl;
  return 0;
}
