#include <bits/stdc++.h>
using namespace std;
long long int putere(long long int x, long long int y) {
  long long int p = 1;
  while (y) {
    if (y % 2) p = (p * x) % 1000000007;
    x = (x * x) % 1000000007;
    y = y / 2;
  }
  return p;
}
int ordin(int p, int k) {
  long long int ord = 1;
  long long int put = k;
  while ((put % p) != 1) {
    put = (put * k) % p;
    ord++;
  }
  return ord;
}
int main() {
  long long int k, p;
  cin >> p >> k;
  if (!k) cout << putere(p, p - 1);
  if (k == 1) cout << putere(p, p);
  if (k > 1) {
    long long int exponent = (p - 1) / ordin(p, k);
    long long int put = putere(p, exponent);
    cout << put;
  }
  return 0;
}
