#include <bits/stdc++.h>
using std::bitset;
using std::cin;
using std::cout;
using std::endl;
using std::map;
using std::multiset;
using std::set;
using std::string;
const long long maxP = 1000000 + 233;
const long long MOD = 1000000007;
long long p, k;
bool vis[maxP];
bool spj() {
  if (k == 0) {
    long long ans = 1;
    for (int i = 0; i < p - 1; ++i) ans = ans * p % MOD;
    cout << ans << endl;
    return true;
  } else if (k == 1) {
    long long ans = 1;
    for (int i = 0; i < p; ++i) ans = ans * p % MOD;
    cout << ans << endl;
    return true;
  } else {
    return false;
  }
}
int main() {
  cin >> p >> k;
  if (spj()) return 0;
  memset(vis, false, sizeof(vis));
  int cnt = 0;
  for (int i = 1; i < p; ++i)
    if (!vis[i]) {
      int x = i;
      while (!vis[x]) vis[x] = true, x = x * k % p;
      ++cnt;
    }
  long long ans = 1;
  while (cnt--) ans = ans * p % MOD;
  cout << ans << endl;
  return 0;
}
