#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
long long k, p, ff[6];
long long lgput(long long b, long long ex) {
  long long sol = 1;
  while (ex) {
    if (ex & 1) sol = (sol * b) % 1000000007;
    b = (b * b) % 1000000007;
    ex >>= 1;
  }
  return sol;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> p >> k;
  if (k == 0) {
    cout << lgput(p, p - 1);
    return 0;
  }
  if (k == 1) {
    cout << lgput(p, p);
    return 0;
  }
  long long ss = k;
  long long m = 1;
  while (ss != 1) {
    ss = (ss * k) % p;
    ++m;
  }
  cout << lgput(p, (p - 1) / m);
  return 0;
}
