#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const double E = 2.718281828459;
const int INF = 2e9;
const long long MOD = 1e9 + 7;
const int MAXN = 1e6 + 1;
long long pot[MAXN];
long long p, k;
bool used[MAXN];
void dfs(int u) {
  used[u] = 1;
  long long nxtu = u * k % p;
  if (!used[nxtu]) dfs(nxtu);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  cin >> p >> k;
  pot[0] = 1;
  for (int i = 1; i <= p; ++i) pot[i] = p * pot[i - 1] % MOD;
  if (k == 0) {
    cout << pot[p - 1] << endl;
    return 0;
  }
  if (k == 1) {
    cout << pot[p] << endl;
    return 0;
  }
  int ans = 0;
  for (int i = 1; i < p; ++i)
    if (!used[i]) {
      dfs(i);
      ++ans;
    }
  cout << pot[ans] << endl;
  return 0;
}
