#include <bits/stdc++.h>
using namespace std;
void SR(int &x) { scanf("%d", &x); }
void SR(long long &x) { scanf("%lld", &x); }
void SR(double &x) { scanf("%lf", &x); }
void SR(char *s) { scanf("%s", s); }
void RI() {}
template <typename I, typename... T>
void RI(I &x, T &...tail) {
  SR(x);
  RI(tail...);
}
void SP(const int x) { printf("%d", x); }
void SP(const long long x) { printf("%lld", x); }
void SP(const double x) { printf("%.16lf", x); }
void SP(const char *s) { printf(s); }
void PS() { puts(""); }
template <typename I, typename... T>
void PS(I &x, T &...tail) {
  putchar(' ');
  SP(x);
  PS(tail...);
}
void PL() { puts(""); }
template <typename I, typename... T>
void PL(const I x, const T... tail) {
  SP(x);
  PS(tail...);
}
const int maxn = 1e6 + 6;
const int MOD = 1e9 + 7;
int main() {
  long long p, k;
  RI(p, k);
  if (k <= 1) {
    long long ans = 1;
    for (int i = 0; i < int(p - 1 + k); i++) ans = (ans * p) % MOD;
    PL(ans);
    return 0;
  }
  int pw = 1;
  for (int x = k; x != 1; x = k * x % p, pw++)
    ;
  long long ans = 1;
  int amt = (p - 1) / pw;
  while (amt--) ans = ans * p % MOD;
  PL(ans);
  return 0;
}
