#include <bits/stdc++.h>
using namespace std;
const long long z = 1000000007;
long long used[1000008];
long long n, k, ans, p;
vector<long long> g[1000003];
void dfs(long long v) {
  used[v] = 1;
  for (int i = 0; i < g[v].size(); i++)
    if (!used[g[v][i]]) {
      used[g[v][i]] = 1;
      dfs(g[v][i]);
    }
}
long long binpow(long long x, long long y) {
  if (x == 0) return 1;
  if (x == 1) return y;
  if (x % 2 == 1) return (y * binpow(x - 1, y) % z);
  if (x % 2 == 0) return (binpow(x / 2, y) * binpow(x / 2, y) % z);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> k;
  for (long long i = 1; i < n; i++) {
    g[k * i % n].push_back(i);
    g[i].push_back(k * i % n);
  }
  for (int i = 1; i < n; i++)
    if (!used[i]) {
      dfs(i);
      ans++;
    }
  if (k == 0) ans = n - 1;
  if (k == 1) ans = n;
  ans = binpow(ans, n);
  cout << ans;
}
