#include <bits/stdc++.h>
using namespace std;
int n, k;
bool vis[1000000];
int ans = 0;
int numberOfColors = 0;
int col[1000000];
int num = 0;
int X[1000000];
inline long long bpow(long long p, long long e, long long m) {
  long long ret = 1;
  for (int a = 0; a < e; ++a) {
    ret = (ret * p) % m;
  }
  return ret;
}
int dfs(int a) {
  if (vis[a]) {
    if (col[a] == -1) {
      col[a] = numberOfColors++;
    }
    return col[a];
  }
  vis[a] = 1;
  ++num;
  col[a] = -1;
  col[a] = dfs(((long long)a * k) % n);
  return col[a];
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n >> k;
  if (k == 0) {
    cout << bpow(n, n - 1, 1000000007);
    return 0;
  }
  for (int a = 0; a < n; ++a) {
    dfs(a);
  }
  for (int a = 0; a < n; ++a) {
    ++X[col[a]];
  }
  for (int a = 0; a < numberOfColors; ++a) {
    if (bpow(k, X[a], n) == 1) ++ans;
  }
  cout << bpow(n, ans, 1000000007);
  return 0;
}
