#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-10;
inline int read() {
  static char ch;
  bool sgn = false;
  while (ch = getchar(), ch < '0' || ch > '9')
    if (ch == '-') sgn = true;
  int res = ch - 48;
  while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
  return sgn ? -res : res;
}
long long pow_mod(long long a, int x, int p) {
  long long ans = 1;
  while (x) {
    if (x % 2) ans *= a, ans %= p;
    x /= 2;
    a *= a;
    a %= p;
  }
  return ans;
}
bool vis[1000005];
int main() {
  int p, k;
  p = read();
  k = read();
  long long ans = 1;
  if (k == 0) {
    ans = pow_mod(p, p - 1, 1000000007);
    cout << ans;
    return 0;
  }
  for (int i = 0; i < p; i++) {
    if (vis[i]) continue;
    vis[i] = 1;
    int x = 1;
    long long j = (long long)i * k % p;
    while (i != j) {
      vis[j] = 1;
      x++;
      j *= k;
      j %= p;
    }
    if (pow_mod(k, x, p) == 1) ans *= p, ans %= 1000000007;
  }
  cout << ans;
}
