#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
const long long int mod = 1e9 + 7;
long long int pow(long long int x, long long int y) {
  long long int sum = 1;
  for (long long int i = 0; i < y; ++i) {
    sum *= x;
    sum %= mod;
  }
  return sum;
}
int main(void) {
  long long int k, p;
  cin >> p >> k;
  if (k == 0) {
    cout << pow(p, p - 1) << endl;
    return 0;
  }
  if (k == 1) {
    cout << pow(p, p) << endl;
    return 0;
  }
  int o = 1;
  long long int prod = k;
  while (prod != 1) {
    prod *= k;
    prod %= p;
    o++;
  }
  assert((p - 1) % o == 0);
  cout << pow(p, (p - 1) / o) << endl;
}
