#include <bits/stdc++.h>
template <typename T>
T identity();
template <typename T, typename Enable = std::true_type>
struct impl__IdentityHelper {};
template <typename T>
struct impl__SampleIdentityHelper {
  static T identity(const T&) { return ::identity<T>(); }
};
template <typename T>
struct impl__IdentityHelper<T, typename std::is_arithmetic<T>::type> {
  static T identity() { return 1; }
};
template <typename T>
T identity(const T& sample) {
  return impl__SampleIdentityHelper<T>::identity(sample);
}
template <typename T>
T identity() {
  return impl__IdentityHelper<T>::identity();
}
template <typename T>
T extendedGcd(T a, T b, T& x, T& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T d = extendedGcd(b % a, a, y, x);
  x -= (b / a) * y;
  return d;
}
template <int mod>
class Zn {
  static_assert(mod > 0, "Mod has to be positive integer");

 public:
  Zn() : value(0) {}
  static Zn valueOf(int value) { return Zn(value % mod); }
  static Zn valueOf(long long value) {
    return Zn(static_cast<int>(value) % mod);
  }
  static Zn rawValueOf(int value) {
    ;
    return Zn(value);
  }
  Zn& operator=(int rhs) { return *this = Zn::valueOf(rhs); }
  Zn& operator=(long long rhs) { return *this = Zn::valueOf(rhs); }
  Zn& operator+=(const Zn& rhs) {
    value += rhs.value;
    if (value >= mod) {
      value -= mod;
    }
    return *this;
  }
  Zn& operator+=(int rhs) { return *this += Zn::valueOf(rhs); }
  Zn& operator+=(long long rhs) { return *this += Zn::valueOf(rhs); }
  Zn& operator-=(const Zn& rhs) {
    value -= rhs.value;
    if (value < 0) {
      value += mod;
    }
    return *this;
  }
  Zn& operator-=(int rhs) { return *this -= Zn::valueOf(rhs); }
  Zn& operator-=(long long rhs) { return *this -= Zn::valueOf(rhs); }
  Zn& operator*=(const Zn& rhs) {
    long long result =
        static_cast<long long>(value) * static_cast<long long>(rhs.value);
    value = static_cast<int>(result % mod);
    return *this;
  }
  Zn& operator*=(int rhs) { return *this *= Zn::valueOf(rhs); }
  Zn& operator*=(long long rhs) { return *this *= Zn::valueOf(rhs); }
  Zn operator-() const {
    if (value == 0) {
      return *this;
    } else {
      return Zn(mod - value);
    }
  }
  Zn& operator/=(const Zn& rhs) { return *this *= rhs.inversed(); }
  Zn& operator/=(int rhs) { return *this /= Zn::valueOf(rhs); }
  Zn& operator/=(long long rhs) { return *this /= Zn::valueOf(rhs); }
  bool operator==(const Zn& rhs) const { return value == rhs.value; }
  Zn inversed() const {
    ;
    int x, y;
    int gcd = extendedGcd(value, mod, x, y);
    (void)gcd;
    ;
    if (x < 0) {
      x += mod;
    }
    return Zn(x);
  }
  template <int m>
  friend std::ostream& operator<<(std::ostream&, const Zn<m>& zn);
  template <int m>
  friend std::istream& operator>>(std::istream&, Zn<m>& zn);
  int intValue() const { return value; }

 private:
  explicit Zn(int value) : value(value) {}
  int value;
};
template <int m>
bool operator==(const Zn<m>& lhs, int rhs) {
  return lhs == Zn<m>::valueOf(rhs);
}
template <int m>
bool operator==(int lhs, const Zn<m>& rhs) {
  return rhs == lhs;
}
template <int m>
bool operator==(const Zn<m>& lhs, long long rhs) {
  return lhs == Zn<m>::valueOf(rhs);
}
template <int m>
bool operator==(long long lhs, Zn<m>& rhs) {
  return rhs == lhs;
}
template <int m>
bool operator!=(const Zn<m>& lhs, const Zn<m>& rhs) {
  return !(lhs == rhs);
}
template <int m>
bool operator!=(const Zn<m>& lhs, int rhs) {
  return !(lhs == rhs);
}
template <int m>
bool operator!=(int lhs, const Zn<m>& rhs) {
  return !(lhs == rhs);
}
template <int m>
bool operator!=(const Zn<m>& lhs, long long rhs) {
  return !(lhs == rhs);
}
template <int m>
Zn<m> operator+(const Zn<m>& lhs, const Zn<m>& rhs) {
  Zn<m> copy = lhs;
  return copy += rhs;
}
template <int m>
Zn<m> operator+(const Zn<m>& lhs, int rhs) {
  Zn<m> copy = lhs;
  return copy += rhs;
}
template <int m>
Zn<m> operator+(int lhs, const Zn<m>& rhs) {
  return rhs + lhs;
}
template <int m>
Zn<m> operator+(const Zn<m>& lhs, long long rhs) {
  Zn<m> copy = lhs;
  return copy += rhs;
}
template <int m>
Zn<m> operator+(long long lhs, const Zn<m>& rhs) {
  return rhs + lhs;
}
template <int m>
Zn<m> operator-(const Zn<m>& lhs, const Zn<m>& rhs) {
  Zn<m> copy = lhs;
  return copy -= rhs;
}
template <int m>
Zn<m> operator-(const Zn<m>& lhs, int rhs) {
  Zn<m> copy = lhs;
  return copy -= rhs;
}
template <int m>
Zn<m> operator-(int lhs, const Zn<m>& rhs) {
  return Zn<m>::valueOf(lhs) - rhs;
}
template <int m>
Zn<m> operator-(const Zn<m>& lhs, long long rhs) {
  Zn<m> copy = lhs;
  return copy -= rhs;
}
template <int m>
Zn<m> operator-(long lhs, const Zn<m>& rhs) {
  return Zn<m>::valueOf(lhs) - rhs;
}
template <int m>
Zn<m> operator*(const Zn<m>& lhs, const Zn<m>& rhs) {
  Zn<m> copy = lhs;
  return copy *= rhs;
}
template <int m>
Zn<m> operator*(const Zn<m>& lhs, int rhs) {
  Zn<m> copy = lhs;
  return copy *= rhs;
}
template <int m>
Zn<m> operator*(int lhs, const Zn<m>& rhs) {
  return rhs * lhs;
}
template <int m>
Zn<m> operator*(const Zn<m>& lhs, long long rhs) {
  Zn<m> copy = lhs;
  return copy *= rhs;
}
template <int m>
Zn<m> operator*(long long lhs, const Zn<m>& rhs) {
  return rhs * lhs;
}
template <int m>
Zn<m> operator/(const Zn<m>& lhs, const Zn<m>& rhs) {
  Zn<m> copy = lhs;
  return copy /= rhs;
}
template <int m>
Zn<m> operator/(const Zn<m>& lhs, int rhs) {
  Zn<m> copy = lhs;
  return copy /= rhs;
}
template <int m>
Zn<m> operator/(int lhs, const Zn<m>& rhs) {
  return Zn<m>::valueOf(lhs) / rhs;
}
template <int m>
Zn<m> operator/(const Zn<m>& lhs, long long rhs) {
  Zn<m> copy = lhs;
  return copy /= rhs;
}
template <int m>
Zn<m> operator/(long long lhs, const Zn<m>& rhs) {
  return Zn<m>::valueOf(lhs) / rhs;
}
template <int m>
std::ostream& operator<<(std::ostream& stream, const Zn<m>& zn) {
  return stream << zn.value;
}
template <int m>
std::istream& operator>>(std::istream& stream, Zn<m>& zn) {
  long long value;
  stream >> value;
  zn.value = static_cast<int>(value % m);
  return stream;
}
template <int m>
struct impl__IdentityHelper<Zn<m>> {
  static Zn<m> identity() { return Zn<m>::valueOf(1); }
};
template <typename T>
T binpow(T base, long long power) {
  ;
  T result = identity<T>(base);
  ;
  while (power > 0) {
    if (power & 1) {
      result *= base;
    }
    power >>= 1;
    base *= base;
  }
  return result;
}
using namespace std;
class TaskB {
 public:
  void solve(std::istream& in, std::ostream& out) {
    int p, k;
    in >> p >> k;
    using Z = Zn<1000000007>;
    if (k == 0) {
      out << binpow(Z::valueOf(p), p - 1);
      return;
    }
    if (k == 1) {
      out << binpow(Z::valueOf(p), p);
      return;
    }
    int power = 1;
    long long cur = k;
    while (cur != Z::rawValueOf(1)) {
      cur *= k;
      cur %= p;
      ++power;
    }
    out << binpow(Z::valueOf(p), (p - 1) / power);
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  TaskB solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(0);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

As behooves any intelligent schoolboy, Kevin Sun is studying psycowlogy, cowculus, and cryptcowgraphy at the Bovinia State University (BGU) under Farmer Ivan. During his Mathematics of Olympiads (MoO) class, Kevin was confronted with a weird functional equation and needs your help. For two fixed integers k and p, where p is an odd prime number, the functional equation states that 

<image>

for some function <image>. (This equation should hold for any integer x in the range 0 to p - 1, inclusive.)

It turns out that f can actually be many different functions. Instead of finding a solution, Kevin wants you to count the number of distinct functions f that satisfy this equation. Since the answer may be very large, you should print your result modulo 109 + 7.

Input

The input consists of two space-separated integers p and k (3 ≤ p ≤ 1 000 000, 0 ≤ k ≤ p - 1) on a single line. It is guaranteed that p is an odd prime number.

Output

Print a single integer, the number of distinct functions f modulo 109 + 7.

Examples

Input

3 2


Output

3


Input

5 4


Output

25

Note

In the first sample, p = 3 and k = 2. The following functions work: 

  1. f(0) = 0, f(1) = 1, f(2) = 2. 
  2. f(0) = 0, f(1) = 2, f(2) = 1. 
  3. f(0) = f(1) = f(2) = 0. 

### Response

```cpp
#include <bits/stdc++.h>
template <typename T>
T identity();
template <typename T, typename Enable = std::true_type>
struct impl__IdentityHelper {};
template <typename T>
struct impl__SampleIdentityHelper {
  static T identity(const T&) { return ::identity<T>(); }
};
template <typename T>
struct impl__IdentityHelper<T, typename std::is_arithmetic<T>::type> {
  static T identity() { return 1; }
};
template <typename T>
T identity(const T& sample) {
  return impl__SampleIdentityHelper<T>::identity(sample);
}
template <typename T>
T identity() {
  return impl__IdentityHelper<T>::identity();
}
template <typename T>
T extendedGcd(T a, T b, T& x, T& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T d = extendedGcd(b % a, a, y, x);
  x -= (b / a) * y;
  return d;
}
template <int mod>
class Zn {
  static_assert(mod > 0, "Mod has to be positive integer");

 public:
  Zn() : value(0) {}
  static Zn valueOf(int value) { return Zn(value % mod); }
  static Zn valueOf(long long value) {
    return Zn(static_cast<int>(value) % mod);
  }
  static Zn rawValueOf(int value) {
    ;
    return Zn(value);
  }
  Zn& operator=(int rhs) { return *this = Zn::valueOf(rhs); }
  Zn& operator=(long long rhs) { return *this = Zn::valueOf(rhs); }
  Zn& operator+=(const Zn& rhs) {
    value += rhs.value;
    if (value >= mod) {
      value -= mod;
    }
    return *this;
  }
  Zn& operator+=(int rhs) { return *this += Zn::valueOf(rhs); }
  Zn& operator+=(long long rhs) { return *this += Zn::valueOf(rhs); }
  Zn& operator-=(const Zn& rhs) {
    value -= rhs.value;
    if (value < 0) {
      value += mod;
    }
    return *this;
  }
  Zn& operator-=(int rhs) { return *this -= Zn::valueOf(rhs); }
  Zn& operator-=(long long rhs) { return *this -= Zn::valueOf(rhs); }
  Zn& operator*=(const Zn& rhs) {
    long long result =
        static_cast<long long>(value) * static_cast<long long>(rhs.value);
    value = static_cast<int>(result % mod);
    return *this;
  }
  Zn& operator*=(int rhs) { return *this *= Zn::valueOf(rhs); }
  Zn& operator*=(long long rhs) { return *this *= Zn::valueOf(rhs); }
  Zn operator-() const {
    if (value == 0) {
      return *this;
    } else {
      return Zn(mod - value);
    }
  }
  Zn& operator/=(const Zn& rhs) { return *this *= rhs.inversed(); }
  Zn& operator/=(int rhs) { return *this /= Zn::valueOf(rhs); }
  Zn& operator/=(long long rhs) { return *this /= Zn::valueOf(rhs); }
  bool operator==(const Zn& rhs) const { return value == rhs.value; }
  Zn inversed() const {
    ;
    int x, y;
    int gcd = extendedGcd(value, mod, x, y);
    (void)gcd;
    ;
    if (x < 0) {
      x += mod;
    }
    return Zn(x);
  }
  template <int m>
  friend std::ostream& operator<<(std::ostream&, const Zn<m>& zn);
  template <int m>
  friend std::istream& operator>>(std::istream&, Zn<m>& zn);
  int intValue() const { return value; }

 private:
  explicit Zn(int value) : value(value) {}
  int value;
};
template <int m>
bool operator==(const Zn<m>& lhs, int rhs) {
  return lhs == Zn<m>::valueOf(rhs);
}
template <int m>
bool operator==(int lhs, const Zn<m>& rhs) {
  return rhs == lhs;
}
template <int m>
bool operator==(const Zn<m>& lhs, long long rhs) {
  return lhs == Zn<m>::valueOf(rhs);
}
template <int m>
bool operator==(long long lhs, Zn<m>& rhs) {
  return rhs == lhs;
}
template <int m>
bool operator!=(const Zn<m>& lhs, const Zn<m>& rhs) {
  return !(lhs == rhs);
}
template <int m>
bool operator!=(const Zn<m>& lhs, int rhs) {
  return !(lhs == rhs);
}
template <int m>
bool operator!=(int lhs, const Zn<m>& rhs) {
  return !(lhs == rhs);
}
template <int m>
bool operator!=(const Zn<m>& lhs, long long rhs) {
  return !(lhs == rhs);
}
template <int m>
Zn<m> operator+(const Zn<m>& lhs, const Zn<m>& rhs) {
  Zn<m> copy = lhs;
  return copy += rhs;
}
template <int m>
Zn<m> operator+(const Zn<m>& lhs, int rhs) {
  Zn<m> copy = lhs;
  return copy += rhs;
}
template <int m>
Zn<m> operator+(int lhs, const Zn<m>& rhs) {
  return rhs + lhs;
}
template <int m>
Zn<m> operator+(const Zn<m>& lhs, long long rhs) {
  Zn<m> copy = lhs;
  return copy += rhs;
}
template <int m>
Zn<m> operator+(long long lhs, const Zn<m>& rhs) {
  return rhs + lhs;
}
template <int m>
Zn<m> operator-(const Zn<m>& lhs, const Zn<m>& rhs) {
  Zn<m> copy = lhs;
  return copy -= rhs;
}
template <int m>
Zn<m> operator-(const Zn<m>& lhs, int rhs) {
  Zn<m> copy = lhs;
  return copy -= rhs;
}
template <int m>
Zn<m> operator-(int lhs, const Zn<m>& rhs) {
  return Zn<m>::valueOf(lhs) - rhs;
}
template <int m>
Zn<m> operator-(const Zn<m>& lhs, long long rhs) {
  Zn<m> copy = lhs;
  return copy -= rhs;
}
template <int m>
Zn<m> operator-(long lhs, const Zn<m>& rhs) {
  return Zn<m>::valueOf(lhs) - rhs;
}
template <int m>
Zn<m> operator*(const Zn<m>& lhs, const Zn<m>& rhs) {
  Zn<m> copy = lhs;
  return copy *= rhs;
}
template <int m>
Zn<m> operator*(const Zn<m>& lhs, int rhs) {
  Zn<m> copy = lhs;
  return copy *= rhs;
}
template <int m>
Zn<m> operator*(int lhs, const Zn<m>& rhs) {
  return rhs * lhs;
}
template <int m>
Zn<m> operator*(const Zn<m>& lhs, long long rhs) {
  Zn<m> copy = lhs;
  return copy *= rhs;
}
template <int m>
Zn<m> operator*(long long lhs, const Zn<m>& rhs) {
  return rhs * lhs;
}
template <int m>
Zn<m> operator/(const Zn<m>& lhs, const Zn<m>& rhs) {
  Zn<m> copy = lhs;
  return copy /= rhs;
}
template <int m>
Zn<m> operator/(const Zn<m>& lhs, int rhs) {
  Zn<m> copy = lhs;
  return copy /= rhs;
}
template <int m>
Zn<m> operator/(int lhs, const Zn<m>& rhs) {
  return Zn<m>::valueOf(lhs) / rhs;
}
template <int m>
Zn<m> operator/(const Zn<m>& lhs, long long rhs) {
  Zn<m> copy = lhs;
  return copy /= rhs;
}
template <int m>
Zn<m> operator/(long long lhs, const Zn<m>& rhs) {
  return Zn<m>::valueOf(lhs) / rhs;
}
template <int m>
std::ostream& operator<<(std::ostream& stream, const Zn<m>& zn) {
  return stream << zn.value;
}
template <int m>
std::istream& operator>>(std::istream& stream, Zn<m>& zn) {
  long long value;
  stream >> value;
  zn.value = static_cast<int>(value % m);
  return stream;
}
template <int m>
struct impl__IdentityHelper<Zn<m>> {
  static Zn<m> identity() { return Zn<m>::valueOf(1); }
};
template <typename T>
T binpow(T base, long long power) {
  ;
  T result = identity<T>(base);
  ;
  while (power > 0) {
    if (power & 1) {
      result *= base;
    }
    power >>= 1;
    base *= base;
  }
  return result;
}
using namespace std;
class TaskB {
 public:
  void solve(std::istream& in, std::ostream& out) {
    int p, k;
    in >> p >> k;
    using Z = Zn<1000000007>;
    if (k == 0) {
      out << binpow(Z::valueOf(p), p - 1);
      return;
    }
    if (k == 1) {
      out << binpow(Z::valueOf(p), p);
      return;
    }
    int power = 1;
    long long cur = k;
    while (cur != Z::rawValueOf(1)) {
      cur *= k;
      cur %= p;
      ++power;
    }
    out << binpow(Z::valueOf(p), (p - 1) / power);
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  TaskB solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(0);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}

```