#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e6 + 500;
const long long mod = 1e9 + 7;
long long f[maxn];
bool vis[maxn];
vector<long long> ger[maxn];
long long poww(long long a, long long b) {
  if (a == 1) return b;
  long long v = poww(a >> 1, b);
  if (a & 1) {
    return (((v * v) % mod) * b) % mod;
  }
  return (v * v) % mod;
}
void dfs(long long a) {
  if (vis[a]) return;
  vis[a] = 1;
  for (long long i = 0; i < ger[a].size(); i++) {
    dfs(ger[a][i]);
  }
}
int main() {
  long long p, k;
  cin >> p >> k;
  if (k == 0) {
    cout << poww(p - 1, p);
    return 0;
  }
  if (k == 1) {
    cout << poww(p, p);
    return 0;
  }
  for (long long i = 0; i < p; i++) {
    ger[i].push_back((i * k) % p);
    ger[(i * k) % p].push_back(i);
  }
  long long mo = 0;
  for (long long i = 0; i < p; i++) {
    if (!vis[i]) {
      dfs(i);
      mo++;
    }
  }
  cout << poww(mo - 1, p);
}
