#include <bits/stdc++.h>
using namespace std;
long long color[1000006];
map<long long, long long> M;
long long power(long long N, long long expo, long long mod) {
  long long ans = 1;
  while (expo) {
    if (expo % 2) {
      ans *= N;
      if (ans >= mod) ans %= mod;
    }
    expo /= 2;
    N *= N;
    if (N >= mod) N %= mod;
  }
  return ans;
}
int main() {
  long long p, k;
  cin >> p >> k;
  long long col = 1;
  long long ans = 1;
  for (int i = 0; i < p; i++) {
    if (!color[i]) {
      long long j = i, cycle = 0;
      while (!color[j]) {
        cycle++;
        color[j] = col;
        j = j * k % p;
      }
      long long x = power(k, cycle, p);
      if (M.count(x))
        ans *= M[x];
      else {
        long long tmp = 0;
        for (int y = 0; y < p; y++)
          if (x * y % p == y) tmp++;
        M[x] = tmp;
        ans *= tmp;
      }
      if (ans >= 1000000007) ans %= 1000000007;
      col++;
    }
  }
  if (k == 0) ans = power(p, p - 1, 1000000007);
  printf("%lld\n", ans);
  return 0;
}
