#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long pow_mod(long long a, long long n) {
  long long ans = 1;
  while (n) {
    if (n & 1) ans = ans * a % MOD;
    a = a * a % MOD;
    n >>= 1;
  }
  return ans;
}
const int maxn = 1000000 + 10;
bool vis[maxn];
long long a[maxn];
int main() {
  long long p, k;
  cin >> p >> k;
  if (k == 0) {
    cout << pow_mod(p, p - 1) << "\n";
    return 0;
  }
  if (k == 1) {
    cout << pow_mod(p, p) << "\n";
    return 0;
  }
  for (long long i = 1; i < p; i++) a[i] = k * i % p;
  long long cnt = 0;
  for (long long i = 1; i < p; i++)
    if (!vis[i]) {
      cnt++;
      for (int j = i; !vis[j]; j = a[j]) vis[j] = true;
    }
  cout << pow_mod(p, cnt) << "\n";
  return 0;
}
