#include <bits/stdc++.h>
using namespace std;
class UnionFind {
 private:
  vector<int> p, rank, setSize;
  int numSets;

 public:
  UnionFind(int n) {
    setSize.assign(n, 1);
    numSets = n;
    rank.assign(n, 0);
    p.assign(n, 0);
    for (int i = 0; i < n; i++) p[i] = i;
  }
  int findSet(int i) {
    if (p[i] == i) return i;
    return (p[i] = findSet(p[i]));
  }
  bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
  void unionSet(int i, int j) {
    if (!isSameSet(i, j)) {
      numSets--;
      int x = findSet(i);
      int y = findSet(j);
      if (rank[x] > rank[y]) {
        p[y] = x;
        setSize[x] += setSize[y];
      } else {
        p[x] = y;
        setSize[y] += setSize[x];
        if (rank[x] == rank[y]) rank[y]++;
      }
    }
  }
  int numDisjointSets() { return numSets; }
  int sizeOfSet(int i) { return setSize[findSet(i)]; }
};
long long int po(long long int a, long long int b) {
  long long int re = 1;
  while (b) {
    if (b % 2) re = (re * a) % 1000000007;
    a = (a * a) % 1000000007;
    b /= 2;
  }
  return re;
}
int main() {
  ios_base::sync_with_stdio(0);
  long long int p, k;
  cin >> p >> k;
  UnionFind u(p);
  for (long long int i = 0; i < p; i++) u.unionSet(i, (k * i) % p);
  if (k == 0)
    cout << po(p, p - 1) << "\n";
  else if (k == 1)
    cout << po(p, p) << "\n";
  else
    cout << po(p, u.numDisjointSets() - 1) << "\n";
  return 0;
}
