#include <bits/stdc++.h>
using namespace std;
const long long inf = 4e18;
const long long maxn = 1e6 + 10;
const long long mod = 1e9 + 7;
long long f[maxn], ans = 1;
bool vis[maxn];
int main() {
  long long p, k;
  cin >> p >> k;
  if (k == 0) {
    for (int i = int(1); i <= int(p - 1); i++) {
      ans = (ans * p) % mod;
    }
    cout << ans;
    return 0;
  }
  for (int i = 0; i < int(p); i++) {
    f[(k * i) % p] = i;
  }
  for (int i = 0; i < int(p); i++) {
    long long tmp = i, num = 1;
    if (!vis[i]) {
      while (!vis[tmp]) {
        num = (num * k) % p;
        vis[tmp] = 1;
        tmp = f[tmp];
      }
      if (num == 1) ans = (ans * p) % mod;
    }
  }
  cout << ans;
}
