#include <bits/stdc++.h>
using namespace std;
int p, k, ans, a;
bool v[1000009];
int main() {
  ans = 1;
  scanf("%d%d", &p, &k);
  for (int i = 1; i < p; i++) {
    if (v[i]) continue;
    ans = (long long)ans * p % 1000000007;
    a = i;
    while (!v[a]) {
      v[a] = 1;
      a = (long long)a * k % p;
    }
  }
  if (k == 1) ans = (long long)ans * p % 1000000007;
  printf("%d\n", ans);
  return 0;
}
