#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 5;
const long long MOD = 1e9 + 7;
const double PI = acos(-1.0);
long long qpow(long long a, long long b) {
  long long sum = 1;
  for (; b >= 1; b >>= 1) {
    if (b & 1) {
      sum *= a;
      sum %= MOD;
    }
    a = a * a % MOD;
  }
  return sum;
}
bool vis[MAX];
int main() {
  long long p, k;
  scanf("%lld %lld", &p, &k);
  if (k == 1)
    printf("%lld\n", qpow(p, p));
  else if (k == 0)
    printf("%lld\n", qpow(p, p - 1));
  else {
    int circle = 0;
    for (long long i = 0; i < p; i++) {
      long long j = i;
      if (vis[j] == false) circle++;
      while (vis[j] == false) {
        vis[j] = true;
        j = k * j % p;
      }
    }
    printf("%lld\n", qpow(p, circle - 1));
  }
  return 0;
}
