#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long b, long long m) {
  long long c = 1;
  for (; b; b >>= 1) {
    if (b & 1) {
      c = (c * a) % m;
    }
    a = (a * a) % m;
  }
  return c;
}
long long solve(long long p, long long k) {
  if (k == 0)
    return power(p, p - 1, 1e9 + 7);
  else if (k == 1)
    return power(p, p, 1e9 + 7);
  long long ord = p - 1;
  for (int i = 2; i <= ord - 1; i++) {
    if (ord % i == 0) {
      if (power(k, ord / i, p) == 1) {
        ord = ord / i;
        i--;
      }
    }
  }
  return power(p, (p - 1) / ord, 1e9 + 7);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long p, k;
  cin >> p >> k;
  cout << solve(p, k);
  return 0;
}
