#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
const long long mod = 1e9 + 7;
long long k, p;
int vis[maxn];
int ans;
void dfs(long long n) {
  if (vis[n]) return;
  vis[n] = 1;
  dfs(k * n % p);
}
long long quickpow(long long n, long long m) {
  long long ans = 1;
  while (m) {
    if (m & 1) ans = (ans * n) % mod;
    m >>= 1;
    n = (n * n) % mod;
  }
  return ans % mod;
}
int main() {
  scanf("%I64d%I64d", &p, &k);
  long long anss = 1;
  if (k == 1) {
    printf("%I64d\n", quickpow(p, p));
    return 0;
  }
  if (k == 0) {
    printf("%I64d\n", quickpow(p, p - 1));
    return 0;
  }
  ans = 0;
  for (long long i = 1; i < p; i++) {
    if (vis[i]) continue;
    dfs(i);
    ans++;
  }
  printf("%I64d\n", quickpow(p, ans));
  return 0;
}
