#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long p, k;
long long mypow(long long x, long long n) {
  long long ret = 1;
  while (n) {
    if (n & 1) {
      ret *= x;
      ret %= mod;
    }
    x *= x;
    x %= mod;
    n >>= 1;
  }
  return ret;
}
int main() {
  cin >> p >> k;
  if (k == 0) {
    cout << mypow(p, p - 1) << endl;
    ;
    return 0;
  }
  if (k == 1) {
    cout << mypow(p, p) << endl;
    return 0;
  }
  long long tmp = k;
  long long m = 1;
  while (m < p) {
    if (tmp == 1) break;
    tmp *= k;
    tmp %= p;
    m++;
  }
  tmp = ceil((p - 1) * 1.0 / m);
  cout << mypow(p, tmp) << endl;
  return 0;
}
