#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void maz(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void miz(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
const int N = 100100, INF = 1e9;
const double EPS = 1e-7;
const int mod = 1e9 + 7;
long long mul(long long a, long long b, long long MOD) { return a * b % MOD; }
long long Pow(long long a, long long x, long long MOD) {
  long long res = 1, tmp = a;
  while (x) {
    if (x & 1) res = mul(res, tmp, MOD);
    tmp = mul(tmp, tmp, MOD);
    x >>= 1;
  }
  return res;
}
int main() {
  int p;
  scanf("%d", &p);
  int k;
  scanf("%d", &k);
  if (k == 0) {
    cout << Pow(p, p - 1, mod) << endl;
  } else if (k == 1) {
    cout << Pow(p, p, mod) << endl;
  } else {
    long long now = k;
    int ct = 1;
    while (now != 1) {
      now = mul(now, k, p), ct++;
    }
    cout << Pow(p, (p - 1) / ct, mod) << endl;
  }
}
