#include <bits/stdc++.h>
using namespace std;
int main() {
  int p = 5, k = 4;
  cin >> p >> k;
  if (k == 1) {
    int a = 1;
    for (int i = 0; i < p; ++i) {
      a = (1LL * p * a) % 1000000007;
    }
    cout << a << endl;
    return 0;
  }
  vector<int> V(p, 0), F(p, 0);
  V[0] = 1;
  int a = 1;
  for (int i = 1; i < p; ++i) {
    F[(1LL * i * k) % p]++;
    if (V[i]) continue;
    int ci = i, tsz = 0;
    while (!V[ci]) {
      tsz++;
      V[ci] = 1;
      ci = (1LL * ci * k) % p;
    }
    a = (1LL * a * p) % 1000000007;
  }
  cout << a << endl;
}
