#include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9 + 7;
const int N = (int)1e5 + 4;
int pw(int a, int k, int p) {
  if (k == 0) {
    return 1;
  }
  int t = pw(a, k / 2, p);
  return ((t * 1LL * t) % p * (k % 2 == 1 ? a : 1)) % p;
}
int main() {
  int p, k;
  cin >> p >> k;
  int ans = 1;
  if (k <= 1) {
    for (int i = (k == 0); i < p; ++i) {
      ans = (ans * 1LL * p) % inf;
    }
    printf("%d", ans);
    return 0;
  }
  int t = 1;
  for (; t < p; ++t) {
    if (pw(k, t, p) == 1) {
      break;
    }
  }
  for (int i = 1; i <= (p - 1) / t; ++i) {
    ans = (ans * 1LL * p) % inf;
  }
  printf("%d", ans);
  return 0;
}
