#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
bool usd[1000009];
int main() {
  long long p, k;
  cin >> p >> k;
  if (k >= 2) {
    long long cnt = 0;
    for (long long i = 1; i < p; ++i)
      if (!usd[i]) {
        long long j = i;
        while (!usd[j]) {
          usd[j] = true;
          j = (j * k) % p;
        }
        ++cnt;
      }
    long long ans = 0;
    for (long long i = 0; i < p; ++i)
      if (i == (k * i) % p) ++ans;
    for (long long i = 0; i < cnt; ++i) ans = (ans * p) % mod;
    cout << ans << endl;
  }
  if (k == 0) {
    long long ans = 1;
    for (long long i = 1; i < p; ++i) ans = (ans * p) % mod;
    cout << ans << endl;
  }
  if (k == 1) {
    long long cnt = 0;
    for (long long i = 0; i < p; ++i)
      if (i == (k * i) % p) ++cnt;
    long long ans = 1;
    for (long long i = 0; i < p; ++i) ans = (ans * cnt) % mod;
    cout << ans << endl;
  }
}
