#include <bits/stdc++.h>
using namespace std;
bool vis[1000006];
int p, k, cnt;
const long long mod = 1000000007LL;
long long pow_mod(long long a, long long n) {
  long long ans = 1LL;
  while (n) {
    if (n & 1) ans = ans * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return ans;
}
int main() {
  cnt = 0;
  long long i = 1;
  long long ans;
  scanf("%d%d", &p, &k);
  if (k >= 1) {
    while (!vis[i]) {
      vis[i] = 1;
      ++cnt;
      i = i * k % p;
    }
    ans = pow_mod(p, (p - 1) / cnt);
    if (cnt == 1) ans = ans * p % mod;
  } else
    ans = pow_mod(p, p - 1);
  printf("%I64d\n", ans);
  return 0;
}
