#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
const int INF = 0x7f7f7f7f;
const int mod = 1000000007;
int cases, MOD;
template <class T>
inline bool read(T& x) {
  int c, ng = 1;
  for (c = getchar(); c <= 32 && ~c; c = getchar())
    ;
  if (!(~c)) return 0;
  if (c == '-') ng = -1, c = getchar();
  for (x = 0; c > 32; x = x * 10 + c - '0', c = getchar())
    ;
  x *= ng;
  return 1;
}
int seed[MAXN];
void init() { memset(seed, -1, sizeof(seed)); }
int Find(int x) { return seed[x] < 0 ? x : seed[x] = Find(seed[x]); }
bool join(int a, int b) {
  a = Find(a);
  b = Find(b);
  if (a == b) return 0;
  if (seed[a] > seed[b]) {
    seed[b] += seed[a];
    seed[a] = b;
  } else {
    seed[a] += seed[b];
    seed[b] = a;
  }
  return 1;
}
long long mult_mod(long long a, long long b, long long p) {
  if (p <= 1e9)
    return a * b % p;
  else if (p <= (long long)1e12)
    return (((a * (b >> 20) % p) << 20) + (a * (b & ((1 << 20) - 1)))) % p;
  else {
    long long d = (long long)floor(a * (long double)b / p + 0.5);
    long long ret = (a * b - d * p) % p;
    if (ret < 0) ret += p;
    return ret;
  }
}
long long pow_mod(long long a, long long k, long long p) {
  long long r = 1;
  a %= p;
  for (; k; k >>= 1, a = mult_mod(a, a, p))
    if (k & 1) r = mult_mod(r, a, p);
  return r;
}
struct mint {
  int x;
  mint() : x(0) {}
  mint(int s) {
    x = s;
    if (x < MOD && x >= 0) return;
    x %= MOD;
    if (x < 0) x += MOD;
  }
  mint(long long s) {
    int ts = s % MOD;
    if (ts < 0) ts += MOD;
    x = ts;
  }
  mint& operator+=(mint t) {
    if ((x += t.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(mint t) {
    if ((x += MOD - t.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(mint t) {
    x = (long long)x * t.x % MOD;
    return *this;
  }
  mint& operator/=(mint t) { return *this *= t.inv(); }
  mint operator-() const {
    if (x) return MOD - x;
    return 0;
  }
  mint operator+(mint t) const { return mint(*this) += t; }
  mint operator-(mint t) const { return mint(*this) -= t; }
  mint operator*(mint t) const { return mint(*this) *= t; }
  mint operator/(mint t) const { return mint(*this) /= t; }
  mint pow(long long k) const {
    mint r = 1, a = x;
    for (; k; k >>= 1, a *= a)
      if (k & 1) r *= a;
    return r;
  }
  mint inv() const { return mint(x).pow(MOD - 2); }
};
int main() {
  int k;
  read(MOD), read(k);
  if (k == 0) {
    printf("%lld\n", pow_mod(MOD, MOD - 1, mod));
  } else if (k == 1) {
    printf("%lld\n", pow_mod(MOD, MOD, mod));
  } else {
    init();
    mint kk = k;
    for (mint i = 1; i.x < MOD; i.x++) {
      mint t = kk * i;
      join(i.x, t.x);
    }
    long long ans = 1;
    for (int i = 1; i < MOD; i++) {
      if (seed[i] < 0) {
        ans = mult_mod(ans, MOD, mod);
      }
    }
    printf("%lld\n", ans);
  }
}
