#include <bits/stdc++.h>
using namespace std;
const long long md = 1000000007;
long long MD1;
long long Pow(long long n, long long k) {
  if (n == 0)
    return 1;
  else {
    long long x = Pow(n / 2, k);
    x = (x * x) % MD1;
    if (n % 2 == 1) x = (x * k) % MD1;
    return x;
  }
}
vector<int> graph;
vector<bool> used;
int dfs(int v) {
  used[v] = true;
  if (!used[graph[v]])
    return dfs(graph[v]) + 1;
  else
    return 1;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n, k;
  cin >> n >> k;
  if (k == 0) {
    long long ans = 1;
    for (int i = 0; i < n - 1; ++i) ans = (ans * n) % md;
    cout << ans;
    return 0;
  }
  MD1 = n;
  graph.resize(n);
  used.resize(n, false);
  for (int i = 0; i < n; ++i) graph[i] = (k * i) % n;
  long long ans = 1;
  for (int i = 0; i < n; ++i)
    if (!used[i]) {
      long long kol = dfs(i);
      if (Pow(kol, k) == 1) ans = (ans * n) % md;
    }
  cout << ans << '\n';
  return 0;
}
