#include <bits/stdc++.h>
using namespace std;
long long int p, k;
int main() {
  cin >> p >> k;
  long long int ans = 1;
  if (k == 0) {
    for (int i = 1; i <= p - 1; i++) ans = (ans * p) % 1000000007;
    cout << ans << endl;
    return 0;
  }
  if (k == 1) {
    for (int i = 1; i <= p; i++) ans = (ans * p) % 1000000007;
    cout << ans << endl;
    return 0;
  }
  long long int m;
  long long int val = 1;
  for (int i = 1; i < p; i++) {
    val = (val * k) % p;
    if (val == 1) {
      m = i;
      break;
    }
  }
  for (int i = 1; i <= (p - 1) / m; i++) ans = (ans * p) % 1000000007;
  cout << ans << endl;
  return 0;
}
