#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long quickpow(long long m, long long n) {
  long long b = 1;
  while (n > 0) {
    if (n & 1) b = (b * m) % mod;
    n = n >> 1;
    m = (m * m) % mod;
  }
  return b;
}
long long a[1000005];
int vis[1000005];
long long p, k;
void dfs(long long x) {
  if (vis[x]) return;
  vis[x] = 1;
  dfs(k * x % p);
}
int main() {
  scanf("%lld%lld", &p, &k);
  if (k == 0) {
    printf("%lld\n", quickpow(p, p - 1));
    return 0;
  }
  if (k == 1) {
    printf("%lld\n", quickpow(p, p));
    return 0;
  }
  long long ans = 0;
  for (int i = 1; i < p; i++) {
    if (vis[i]) continue;
    dfs(i);
    ans++;
  }
  printf("%lld\n", quickpow(p, ans));
}
