#include <bits/stdc++.h>
using namespace std;
template <typename T>
void pr(vector<T> &v) {
  for (int i = 0; i < (int)(v).size(); i++) cout << v[i] << " ";
  cout << '\n';
  ;
}
template <typename T>
void pr(vector<vector<T>> &v) {
  for (int i = 0; i < (int)(v).size(); i++) {
    pr(v[i]);
  }
}
template <typename T>
void re(T &x) {
  cin >> x;
}
template <typename T>
void re(vector<T> &a) {
  for (int i = 0; i < (int)(a).size(); i++) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &...rest) {
  re(first);
  re(rest...);
}
template <typename T>
void pr(T x) {
  cout << x << '\n';
  ;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &...rest) {
  cout << first << " ";
  pr(rest...);
  cout << '\n';
  ;
}
void ps() {
  cout << '\n';
  ;
}
template <class T, class... Ts>
void ps(const T &t, const Ts &...ts) {
  cout << t;
  if (sizeof...(ts)) cout << " ";
  ps(ts...);
}
const long long MOD = 1000000007;
long double PI = 4 * atan(1);
long double eps = 1e-12;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long n, k;
  cin >> n >> k;
  long long powk = k;
  long long exp = 1;
  long long nexp = n - 1;
  if (k == 1) {
    nexp = n;
  }
  if (k != 0 && k != 1) {
    while (powk % n != 1) {
      powk *= k;
      powk %= n;
      exp++;
    }
    nexp = (n - 1) / exp;
  }
  long long powp = 1;
  for (int i = 0; i < nexp; i++) {
    powp *= n;
    powp %= MOD;
  }
  cout << powp << '\n';
  ;
}
