#include <bits/stdc++.h>
using namespace std;
long long p, k;
int used[1000005];
long long mod = 1e9 + 7;
int par[1000005];
int find_par(int x) {
  if (x == par[x]) return x;
  return par[x] = find_par(par[x]);
}
void union_sets(int x, int y) {
  x = find_par(x);
  y = find_par(y);
  par[y] = x;
}
int main() {
  long long i;
  cin >> p >> k;
  long long br = 0;
  long long f = 1, x;
  for (i = 1; i < p; i++) {
    par[i] = i;
  }
  long long y;
  long long z;
  for (i = 0; i < p; i++) {
    if (used[i]) continue;
    x = i;
    z = 1;
    while (!used[x]) {
      z *= k;
      z %= p;
      used[x] = 1;
      y = (x * k) % p;
      x = y;
    }
    if (x == i && z == 1) br++;
  }
  if (k == 0) br = p - 1;
  for (i = 0; i < br; i++) {
    f = (f * p) % mod;
  }
  cout << f << endl;
  return 0;
}
