#include <bits/stdc++.h>
using namespace std;
long long N = 1e9 + 7;
long long n, m, l, i, j, r, k, s = 1, t, color[5000000];
void dfs(long long x) {
  if (color[x] == 1) return;
  color[x] = 1;
  dfs((x * k) % n);
}
int main() {
  cin >> n >> k;
  for (i = 1; i < n; i++)
    if (color[i] == 0) dfs(i), s = ((s * n) % N);
  if (k == 1) s = (s * n) % N;
  cout << s;
  return 0;
}
