#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
const int MOD = 1000000007;
long long m, k, p, ans, powp[N], powk[N];
int main() {
  scanf("%d%d", &p, &k);
  powp[0] = powk[0] = 1;
  for (int i = 1; i <= p; i++) {
    powp[i] = (powp[i - 1] * p) % MOD;
    powk[i] = (powk[i - 1] * k) % p;
    if ((powk[i] == 1) && (m == 0)) m = i;
  }
  if (k == 0)
    ans = powp[p - 1];
  else if (k == 1)
    ans = powp[p];
  else
    ans = powp[(p - 1) / m];
  printf("%I64d\n", ans);
  return 0;
}
