#include <bits/stdc++.h>
using namespace std;
vector<int> p, rk;
long long int Pow(long long int a, long long int b) {
  if (b == 0) return 1;
  long long int temp = Pow(a, b / 2);
  long long int prod = (temp * temp) % 1000000007;
  if (b % 2) prod = (prod * a) % 1000000007;
  return prod;
}
int findParent(int nd) {
  return (p[nd] == nd ? nd : p[nd] = findParent(p[nd]));
}
void Union(int a, int b) {
  int x = findParent(a), y = findParent(b);
  if (x != y) {
    if (rk[x] < rk[y])
      p[x] = y;
    else {
      p[y] = x;
      rk[x] += (rk[x] == rk[y]);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int pi, k;
  cin >> pi >> k;
  if (k == 0) {
    long long int ans = Pow(pi, pi - 1);
    cout << ans;
    return 0;
  }
  if (k == 1) {
    long long int ans = Pow(pi, pi);
    cout << ans;
    return 0;
  }
  p.resize(pi);
  iota(p.begin(), p.end(), 0);
  rk.resize(pi);
  fill(rk.begin(), rk.end(), 1);
  for (int i = 0; i < pi; i += 1) Union(i, ((long long int)i * k) % pi);
  for (int i = 0; i < pi; i += 1) p[i] = findParent(i);
  set<int> s;
  for (int i = 0; i < pi; i += 1) s.insert(p[i]);
  long long int ans = Pow(pi, (int)s.size() - 1);
  cout << ans;
}
