#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int p, k, ans, vis[1 << 20];
int solve() {
  ans = 1;
  if (!k) {
    for (int i = 1; i < p; ++i) ans = 1LL * ans * p % mod;
  } else if (k == 1) {
    for (int i = 1; i <= p; ++i) {
      ans = 1LL * ans * p % mod;
    }
  } else {
    for (int i = 0; i < p; ++i) {
      if (!vis[i]) {
        int len = 0;
        while (!vis[i]) {
          vis[i] = 1;
          ++len;
          i = 1LL * i * k % p;
        }
        if (i != 0) ans = 1LL * ans * p % mod;
      }
    }
  }
  return ans;
}
int32_t main() {
  cin >> p >> k;
  cout << solve();
}
