#include <bits/stdc++.h>
using namespace std;
int p, k, seen[1000100];
void dfs(int node) {
  int next = (int)((node * 1LL * k) % p);
  seen[node] = 1;
  if (not seen[next]) {
    dfs(next);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> p >> k;
  int tot = 0;
  for (int i = 1; i < p; i++) {
    if (not seen[i]) {
      tot++;
      seen[i] = 1;
      dfs(i);
    }
  }
  long long ans = 1;
  for (int i = 0; i < tot; i++) {
    ans *= p;
    ans %= 1000000007;
  }
  if (k == 1) {
    ans *= p;
    ans %= 1000000007;
  }
  cout << ans << "\n";
}
