#include <bits/stdc++.h>
using namespace std;
long long mu(long long a, long long b) {
  if (b == 0) return 1 % 1000000007LL;
  if (b == 1) return a % 1000000007LL;
  long long k = mu(a, b / 2);
  if (b % 2) return (((k * k) % 1000000007LL) * a) % 1000000007LL;
  return (k * k) % 1000000007LL;
}
int main() {
  ios::sync_with_stdio(0);
  long long p, k;
  cin >> p >> k;
  if (k == 0)
    cout << mu(p, p - 1);
  else if (k == 1)
    cout << mu(p, p);
  else {
    long long m = 1;
    long long cur = k;
    for (; cur != 1; m++) cur = (cur * k) % p;
    cout << mu(p, (p - 1) / m);
  }
  return 0;
}
