#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long p, k, cnt = 0;
bool vis[1000005];
long long power(long long a, long long n, long long mod) {
  return (n == 0)
             ? 1
             : (power(a * a % mod, n / 2, mod) * ((n % 2 == 1) ? a : 1) % mod);
}
int main() {
  cin >> p >> k;
  if (k == 0)
    cout << power(p, p - 1, mod) << endl;
  else if (k == 1)
    cout << power(p, p, mod) << endl;
  else {
    long long ord = p;
    for (long long i = 1; i * i <= p - 1; i++) {
      if ((p - 1) % i == 0) {
        if (power(k, i, p) == 1LL) ord = min(ord, i);
        if (power(k, (p - 1) / i, p) == 1LL) ord = min(ord, (p - 1) / i);
      }
    }
    cout << power(p, (p - 1) / ord, mod) << endl;
  }
  return 0;
}
