#include <bits/stdc++.h>
using namespace std;
long long P, K;
long long ans = 1ll;
int main() {
  if (fopen("cf604d.in", "r")) {
    freopen("cf604d.in", "r", stdin);
    freopen("cf604d.out", "w", stdout);
  }
  cin >> P >> K;
  if (K == 0ll) {
    for (long long i = 1; i < P; i++) {
      ans *= P;
      ans %= 1000000007ll;
    }
  } else if (K == 1ll) {
    for (long long i = 0; i < P; i++) {
      ans *= P;
      ans %= 1000000007ll;
    }
  } else {
    long long t = 1;
    long long ord = 0ll;
    do {
      t *= K;
      t %= P;
      ord++;
    } while (t != 1ll);
    long long po = (P - 1) / ord;
    for (int i = 0; i < po; i++) {
      ans *= P;
      ans %= 1000000007ll;
    }
  }
  cout << ans << '\n';
  return 0;
}
