#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
bool tb[1000009];
void dfs(long long int x, long long int p, long long int k) {
  if (tb[x]) return;
  tb[x] = true;
  dfs((x * k) % p, p, k);
}
int main() {
  long long int p, k, wyn = 0;
  long long int w = 1, pom;
  scanf("%lld%lld", &p, &k);
  for (int i = 1; i < p; ++i)
    if (!tb[i]) {
      ++wyn;
      dfs(i, p, k);
    }
  for (int i = 0; i < wyn; ++i) w = (w * p) % MOD;
  if (k == 1) w = (w * p) % MOD;
  printf("%lld", w);
  return 0;
}
