#include <bits/stdc++.h>
using namespace std;
int A[1000005];
long long expo(long long a, int n) {
  if (n == 0) return 1;
  long long temp = expo(a, n / 2LL);
  temp = (temp * temp) % 1000000007;
  if (n % 2 == 1) temp = (temp * a) % 1000000007;
  return temp;
}
int main() {
  int p, k;
  scanf("%d%d", &p, &k);
  memset(A, 0, sizeof(A));
  int count_chains = 0;
  if (k == 0) {
    int ans = expo(p, p - 1);
    printf("%d\n", ans);
    return 0;
  }
  for (int x = 1; x < p; x++) {
    if (A[x] == 1) continue;
    A[x] = 1;
    count_chains++;
    while (1) {
      long long t = x;
      t = ((long long)k * x) % (long long)p;
      x = t;
      if (A[x] == 1) break;
      A[x] = 1;
    }
  }
  if (k == 1) count_chains++;
  int ans = expo(p, count_chains);
  printf("%d\n", ans);
  return 0;
}
