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