#include <bits/stdc++.h>
using namespace std;
long long size[1000004], initial[1000004];
long long power(long long a, long long b, long long m = 1000000007) {
  long long x = 1;
  a %= m;
  while (b) {
    if ((1 & b)) x = x * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return x;
}
int root(int x) {
  if (initial[x] == x) return x;
  return initial[x] = root(initial[x]);
}
void weighted_union(int x, int y) {
  x = root(x), y = root(y);
  if (size[x] > size[y]) {
    initial[y] = x;
    size[x] += size[y];
  } else {
    initial[y] = x;
    size[x] += size[y];
  }
}
int main() {
  int p, k, ans = 0;
  cin >> p >> k;
  if (k == 0)
    cout << power(p, p - 1);
  else if (k == 1)
    cout << power(p, p);
  else {
    for (int i = 1; i < p; i++) initial[i] = i, size[i] = 1;
    for (int i = 1; i < p; i++) weighted_union(i, (1LL * i * k) % p);
    for (int i = 1; i < p; i++)
      if (initial[i] == i) ans++;
    cout << power(p, ans);
  }
  return 0;
}
