#include <bits/stdc++.h>
const int N = 1000100;
const int M = 1000000007;
int a[N], c[N];
int p, k, m, cnt;
void go(int k, int col) {
  c[k] = col;
  if (c[a[k]] == 0) go(a[k], col);
}
int main() {
  scanf("%d%d", &p, &k);
  if (k == 0) m = p - 1;
  if (k == 1) m = p;
  if (k > 1) {
    for (int i = 0; i < p; ++i) a[i] = 1LL * i * k % p;
    for (int i = 0; i < p; ++i)
      if (c[i] == 0) {
        ++m;
        go(i, m);
      }
    --m;
  }
  int s = p;
  for (int i = 1; i < m; ++i) s = 1LL * s * p % M;
  printf("%d\n", s);
  return 0;
}
