#include <bits/stdc++.h>
using namespace std;
const int N = 1000000 + 10;
const int MOD = 1000000007;
bool vis[N];
int cnt[N];
int main() {
  int res, p, k, s, i, j;
  cin >> p >> k;
  if (k == 0) {
    res = 1;
    for (i = 1; i < p; i++) res = 1LL * res * p % MOD;
    cout << res << endl;
    return 0;
  }
  cnt[1] = 1;
  for (i = 1; i < p; i++)
    if (!vis[i]) {
      s = 1;
      vis[i] = true;
      for (j = 1LL * i * k % p; j != i; j = 1LL * j * k % p, s++) vis[j] = true;
      cnt[s]++;
    }
  res = 1;
  for (i = 1; i <= p; i++)
    if (cnt[i]) {
      s = 0;
      for (j = 1; j * j <= i; j++)
        if (i % j == 0) {
          s += j * cnt[j];
          if (j != i / j) s += i / j * cnt[i / j];
        }
      for (j = 0; j < cnt[i]; j++) res = 1LL * res * s % MOD;
    }
  cout << res << endl;
  return 0;
}
