#include <bits/stdc++.h>
using namespace std;
vector<int> dv;
int vis[1000010];
int perm[1000010];
int c[1000010];
void polya(int n) {
  memset(vis, 0, sizeof vis);
  for (int i = 0; i < n; i++) {
    if (!vis[i]) {
      int j = i;
      int ans = 0;
      while (!vis[j]) {
        vis[j] = 1;
        j = perm[j];
        ans++;
      }
      c[ans]++;
      dv.push_back(ans);
    }
  }
}
long long fac[1000010];
const int mod = 1e9 + 7;
int main() {
  fac[0] = 1;
  int p, k;
  cin >> p >> k;
  if (!k) {
    long long ans = 1;
    for (int i = 1; i < p; i++) ans = ans * p % mod;
    cout << ans << endl;
    return 0;
  }
  for (int i = 0; i < p; i++) perm[i] = (long long)i * k % p;
  polya(p);
  long long ans = 1, tmp;
  for (int i = 0; i < dv.size(); i++) {
    tmp = 0;
    for (int j = 1; j <= dv[i]; j++) {
      if (dv[i] % j == 0 && c[j]) {
        tmp += (long long)c[j] * j % mod;
      }
    }
    ans = (ans * tmp) % mod;
  }
  cout << ans << endl;
  return 0;
}
