#include <bits/stdc++.h>
using namespace std;
int G[1000100];
bool B[1000100];
long long mod = 1e9 + 7;
void dfs(int u) {
  B[u] = true;
  if (!B[G[u]]) {
    dfs(G[u]);
  }
}
long long po(int P, int R) {
  long long ret = 1;
  long long p = P;
  while (R) {
    if (R & 1) {
      ret *= p;
      ret %= mod;
    }
    p = (p * p) % mod;
    R >>= 1;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  int P;
  cin >> P;
  int K;
  cin >> K;
  if (K == 1) {
    cout << po(P, P) << '\n';
    return 0;
  } else if (K == 0) {
    cout << po(P, P - 1) << '\n';
    return 0;
  }
  for (int i = 1; i < P; i++) {
    int tp = (1LL * K * i) % P;
    G[i] = tp;
  }
  int count = 0;
  for (int i = 1; i < P; i++) {
    if (!B[i]) {
      dfs(i);
      count++;
    }
  }
  cout << po(P, count) << '\n';
  return 0;
}
