#include <bits/stdc++.h>
using namespace std;
struct DSU {
  int n, x;
  vector<long long> p, r, sz;
  DSU(int N) {
    n = N;
    x = N - 1;
    sz.assign(N, 1);
    p.assign(N, 0);
    r.assign(N, 1);
    for (int i = 0; i < N; i++) p[i] = i;
  }
  int findset(int i) { return (p[i] == i) ? i : (p[i] = findset(p[i])); }
  bool issameset(int i, int j) { return findset(i) == findset(j); }
  void unionset(int i, int j) {
    int p1 = findset(i);
    int p2 = findset(j);
    if (p1 != p2) {
      x--;
      if (r[p1] >= r[p2]) {
        p[p2] = p1;
        sz[p1] += sz[p2];
        if (r[p1] == r[p2]) r[p1]++;
      } else {
        p[p1] = p2;
        sz[p2] += sz[p1];
      }
    }
  }
  void disp() {
    for (int i = 0; i < n; i++) cout << p[i] << ' ';
    cout << '\n';
  }
  int getsize(int i) { return sz[findset(i)]; }
  int noofdisjointsets() { return x; }
};
const long long MOD = 1e9 + 7;
struct mint {
  typedef decay<decltype(MOD)>::type T;
  T v;
  explicit operator T() const { return v; }
  mint() { v = 0; }
  mint(long long _v) {
    v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
    if (v < 0) v += MOD;
  }
  friend bool operator==(const mint& a, const mint& b) { return a.v == b.v; }
  friend bool operator!=(const mint& a, const mint& b) { return !(a == b); }
  friend bool operator<(const mint& a, const mint& b) { return a.v < b.v; }
  mint& operator+=(const mint& m) {
    if ((v += m.v) >= MOD) v -= MOD;
    return *this;
  }
  mint& operator-=(const mint& m) {
    if ((v -= m.v) < 0) v += MOD;
    return *this;
  }
  mint& operator*=(const mint& m) {
    v = (long long)v * m.v % MOD;
    return *this;
  }
  mint& operator/=(const mint& m) { return (*this) *= inv(m); }
  friend mint pow(mint a, long long p) {
    mint ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mint inv(const mint& a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
  }
  mint operator-() const { return mint(-v); }
  mint& operator++() { return *this += 1; }
  mint& operator--() { return *this -= 1; }
  friend mint operator+(mint a, const mint& b) { return a += b; }
  friend mint operator-(mint a, const mint& b) { return a -= b; }
  friend mint operator*(mint a, const mint& b) { return a *= b; }
  friend mint operator/(mint a, const mint& b) { return a /= b; }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long n, x, t, m, y, z, k;
  mint p;
  cin >> p.v >> k;
  DSU s(p.v);
  mint ans = 1;
  if (k == 0) {
    cout << pow(p, p.v - 1).v;
  } else if (k == 1) {
    cout << pow(p, p.v).v;
  } else {
    for (int i = 0; i < p.v; i++) {
      s.unionset(i, (i * k) % p.v);
    }
    cout << pow(p, s.noofdisjointsets()).v;
  }
  return 0;
}
