#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
inline long long int fastexpo(long long int base, long long int expo) {
  long long int result = 1;
  while (expo > 0) {
    if (expo % 2 == 1) {
      result = (result * base) % mod;
    }
    expo = expo >> 1;
    base = (base * base) % mod;
  }
  return result;
}
vector<int> g[1000001];
bool reached[1000001];
inline void dfs(int pos, int prev) {
  reached[pos] = true;
  for (int i = 0; i < g[pos].size(); i++) {
    if (!reached[g[pos][i]]) {
      dfs(g[pos][i], pos);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  long long p, k;
  cin >> p >> k;
  if (k == 1) {
    cout << fastexpo(p, p) << "\n";
    return 0;
  }
  if (k == 0) {
    cout << fastexpo(p, p - 1) << "\n";
    return 0;
  }
  for (long long i = 1; i < p; i++) {
    long long y = (k * i) % p;
    g[y].push_back(i);
    g[i].push_back(y);
  }
  long long ans = 1;
  for (int i = 1; i < p; i++) {
    if (!reached[i]) {
      ans = (ans * p) % mod;
      dfs(i, 0);
    }
  }
  cout << ans << "\n";
}
