#include <bits/stdc++.h>
int main() {
  int m = 1, k, p;
  std::cin >> p >> k;
  if (k == 0)
    m = p - 1;
  else if (k == 1)
    m = p;
  else {
    long long x = k;
    while (x != 1) {
      x = x * k % p;
      m++;
    }
    m = (p - 1) / m;
  }
  long long res = 1;
  while (m--) res = res * p % 1000000007;
  std::cout << res;
}
