#include <bits/stdc++.h>
using namespace std;
const long long N = 1000000 + 10;
const long long mod = 1e9 + 7;
long long p, k, to[N];
bool vis[N];
map<long long, long long> loop;
long long calc(long long len) {
  long long ret = 0;
  for (__typeof((loop).begin()) it = (loop).begin(); it != (loop).end(); it++)
    if (len % (it->first) == 0) ret += it->first * it->second;
  return ret % mod;
}
int main() {
  scanf("%I64d%I64d", &p, &k);
  if (k == 0) {
    long long ans = 1;
    for (long long i = 1; i <= (p - 1); i++) ans = ans * p % mod;
    printf("%d\n", ans);
    return 0;
  }
  for (long long i = (0); i <= (p - 1); i++) to[i] = k * i % p;
  for (long long i = (0); i <= (p - 1); i++)
    if (!vis[i]) {
      long long cnt = 0;
      for (long long j = i; !vis[j]; j = to[j]) {
        cnt++;
        vis[j] = true;
      }
      loop[cnt]++;
    }
  long long ans = 1;
  for (__typeof((loop).begin()) it = (loop).begin(); it != (loop).end(); it++) {
    long long mult = calc(it->first);
    for (long long j = 1; j <= (it->second); j++) ans = ans * mult % mod;
  }
  printf("%I64d\n", ans);
  return 0;
}
