#include <bits/stdc++.h>
using namespace std;
long long p, k, i, t, ans, ii;
bool bo[3000000], b;
long long ksm(long long x, long long y) {
  if (y == 0) return 1;
  if (y == 1) return x;
  long long k = ksm(x, y / 2);
  if (y % 2 == 1)
    return (k * k * x % 1000000007);
  else
    return (k * k % 1000000007);
}
int main() {
  scanf("%I64d %I64d", &p, &k);
  ans = 1;
  if (k == 0) {
    for (i = 1; i < p; i++) ans = ans * p % 1000000007;
    printf("%I64d", ans);
    return 0;
  }
  if (k == 1) {
    for (i = 1; i <= p; i++) ans = ans * p % 1000000007;
    printf("%I64d", ans);
    return 0;
  }
  for (i = 1; i < p; i++) {
    ii = i;
    b = false;
    while (!bo[(ii * k) % p]) {
      bo[(ii * k) % p] = true;
      ii = (ii * k) % p;
      b = true;
    }
    if (b) t++;
  }
  for (i = 1; i <= t; i++) ans = ans * p % 1000000007;
  printf("%I64d", ans);
}
