#include <bits/stdc++.h>
using namespace std;
long long p, k;
long long pw(long long a, long long b, long long md) {
  long long rez = 1;
  while (b) {
    if (b % 2) rez = (rez * a) % md;
    a = (a * a) % md;
    b /= 2;
  }
  return rez;
}
int main() {
  cin >> p >> k;
  if (k == 1) {
    cout << pw(p, p, 1000000007);
    return 0;
  }
  if (k == 0) {
    cout << pw(p, p - 1, 1000000007);
    return 0;
  }
  long long m = 1;
  while (pw(k, m, p) != 1) m++;
  long long x = (p - 1) / m;
  cout << pw(p, x, 1000000007);
  return 0;
}
