#include <bits/stdc++.h>
using namespace std;
long long int pow1(int p, int x) {
  if (x == 0) return 1;
  if (x == 1) return p;
  return (p * (pow1(p, x - 1)) % 1000000007) % 1000000007;
}
int main() {
  int p, k;
  cin >> p >> k;
  if (k == 0) {
    cout << pow1(p, p - 1) << endl;
  } else if (k == 1) {
    cout << pow1(p, p) << endl;
  } else {
    int ord = 1;
    int x = k;
    long long int y = k;
    while (y != 1 && ord < p + 1) {
      ord++;
      y = y * k % p;
    }
    cout << pow1(p, (p - 1) / ord) << endl;
  }
  return 0;
}
