#include <bits/stdc++.h>
volatile bool isLocalTestEnabled = 0;
bool g_isLocalPrintEnabled = (bool)(0);
template <typename T>
void UpdateMin(T& a, const T b) {
  a = std::min(a, b);
}
template <typename T>
void UpdateMax(T& a, const T b) {
  a = std::max(a, b);
}
const long double Pi = std::atan(1.0L) * 4.0L;
static const long double Eps = 1.0e-09;
template <typename T>
bool IsEqual(const T a, const T b) {
  return std::abs(a - b) < Eps;
}
template <typename T>
bool IsGreater(const T a, const T b) {
  return a > b + Eps;
}
template <typename T>
bool IsLess(const T a, const T b) {
  return a + Eps < b;
}
template <typename T>
bool IsGreaterEqual(const T a, const T b) {
  return !IsLess(a, b);
}
template <typename T>
bool IsLessEqual(const T a, const T b) {
  return !IsGreater(a, b);
}
template <typename T>
std::string ToStr(const T& val) {
  std::ostringstream ostr;
  ostr << val;
  return ostr.str();
}
template <typename T>
bool FromStr(const std::string& str, T& val) {
  std::istringstream istr(str);
  istr >> val;
  return !!istr;
}
template <typename T>
std::istream& operator>>(std::istream& ist, std::vector<T>& data) {
  ;
  for (size_t i = 0; i < data.size(); i++) {
    ist >> data[i];
  }
  return ist;
}
template <typename T>
T Read(std::istream& ist) {
  ;
  T val;
  ist >> val;
  return val;
}
template <typename T>
std::ostream& operator<<(std::ostream& ost, const std::vector<T>& data) {
  for (size_t i = 0; i < data.size(); i++) {
    if (i != 0) {
      ost << ' ';
    }
    ost << data[i];
  }
  return ost;
}
template <size_t id>
class StopWatch {};
const uint64_t Mod = 1000000007;
template <typename T>
static T FastPow(const T a, const T p) {
  T res = 1;
  T mask = 1;
  T powPart = a;
  const size_t bitsCount = sizeof(T) * 8;
  for (size_t i = 0; i < bitsCount; i++) {
    if (p & mask) {
      res *= powPart;
      res %= Mod;
    }
    mask <<= 1;
    powPart *= powPart;
    powPart %= Mod;
  }
  return res;
}
bool Solve(std::istream& ist, std::ostream& ost, const bool multipleTestMode) {
  StopWatch<1> sw;
  (void)sw;
  uint64_t p, k;
  ist >> p >> k;
  if (multipleTestMode && !ist) return false;
  if (!g_isLocalPrintEnabled) {
  } else
    std::cout << std::endl << "Next test: " << p << " " << k << std::endl;
  if (k == 0) {
    const uint64_t ans = FastPow(p, p - 1);
    ost << ans << std::endl;
    return multipleTestMode;
  }
  if (k == 1) {
    const uint64_t ans = FastPow(p, p);
    ost << ans << std::endl;
    return multipleTestMode;
  }
  uint64_t groups = 0;
  std::vector<size_t> used(p + 1);
  uint64_t ans = 1;
  for (uint64_t x = 1; x < p; x++) {
    if (used[x]) continue;
    groups += 1;
    ans *= p;
    ans %= Mod;
    used[x] = 1;
    uint64_t v = x;
    while (!used[v * k % p]) {
      used[v * k % p] = 1;
      v = v * k % p;
    }
  }
  ost << ans << std::endl;
  return multipleTestMode;
}
int main(int argc, const char* argv[]) {
  std::ios_base::sync_with_stdio(false);
  std::istream* ist = &std::cin;
  std::ostream* ost = &std::cout;
  std::unique_ptr<std::istream> fileInput;
  if (argc > 1) {
    fileInput.reset(new std::ifstream(argv[1]));
    if (!(*fileInput)) {
      std::cout << "File not found: " << argv[1] << std::endl;
    }
    ist = fileInput.get();
  }
  Solve(*ist, *ost, false);
}
