#include <bits/stdc++.h>
using namespace std;
long long p, k, ans, cnt, num[1000005], check[1000005], a, now, fac[100005];
int main() {
  fac[0] = fac[1] = 1;
  ans = 1;
  scanf("%lld%lld", &p, &k);
  if (k == 0) {
    for (int i = 1; i < p; i++) {
      ans *= p;
      ans %= 1000000007;
    }
    printf("%lld", ans);
    return 0;
  }
  if (k == 1) {
    for (int i = 0; i < p; i++) {
      ans *= p;
      ans %= 1000000007;
    }
    printf("%lld", ans);
    return 0;
  }
  check[0] = 1;
  for (int i = 1; i < p; i++) {
    a = (k * i) % p;
    num[i] = a;
  }
  for (int i = 1; i < p; i++) {
    if (!check[i]) {
      now = i;
      while (!check[now]) {
        check[now] = 1;
        now = num[now];
        cnt++;
      }
    }
    if (cnt > 1) ans *= p;
    cnt = 0;
    ans %= 1000000007;
  }
  printf("%lld", ans);
}
