#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int p, k;
inline int fpow(long long b, long long e) {
  long long pow = b;
  long long res = 1;
  while (e) {
    if (e & 1) {
      res *= pow;
      res %= mod;
    }
    pow *= pow;
    pow %= mod;
    e >>= 1;
  }
  return res;
}
void input() { cin >> p >> k; }
void solve() {
  long long res = 1;
  long long cnt = 0;
  if (k) {
    do {
      res *= k;
      res %= p;
      cnt++;
    } while (res != 1);
  } else {
    cnt = 1;
  }
  cout << fpow(p, (p - 1) / cnt + (k == 1)) << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  input();
  solve();
}
