#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int block_size = 360;
const long long mod = 1e9 + 7;
const long double eps = 1e-9;
long long p, k;
long long fast(long long a, long long b, long long mod) {
  long long ans = 1;
  while (b > 0) {
    if (b % 2 == 0) {
      b /= 2;
      a = a * a % mod;
    } else {
      b--;
      ans = ans * a % mod;
    }
  }
  return ans;
}
vector<int> test;
void read() { cin >> p >> k; }
void get_factors() {
  for (long long i = 1; i * i <= p - 1; i++) {
    if ((p - 1) % i == 0) {
      test.push_back(i);
      test.push_back((p - 1) / i);
    }
  }
  sort(begin(test), end(test));
}
long long get_order() {
  for (long long i = 0; i < test.size(); i++) {
    if (fast(k, test[i], p) == 1) {
      return test[i];
    }
  }
  return -1;
}
void solve() {
  read();
  if (k == 1) {
    cout << fast(p, p, mod) << endl;
    return;
  }
  get_factors();
  if (k == 0) {
    cout << fast(p, p - 1, mod) << endl;
  } else {
    long long index = get_order();
    cout << fast(p, (p - 1) / index, mod);
  }
}
int main() {
  solve();
  return 0;
}
