#include <bits/stdc++.h>
using namespace std;
long long ans = 0;
long long p, k;
bool done[1000000];
long long to(long long x) { return x * k % p; }
long long power(long long base, long long exp) {
  int ans = 1;
  while (exp) {
    if (exp & 1) ans = ans * base % 1000000007;
    base = base * base % 1000000007;
    exp = exp >> 1;
  }
  return ans;
}
int main() {
  scanf("%I64d%I64d", &p, &k);
  if (k == 0) {
    printf("%I64d", power(p, p - 1));
  } else {
    for (int i = 0; i < p; ++i) {
      if (k * i % p == i) ++ans;
    }
    for (int i = 1; i < p; ++i)
      if (!done[i]) {
        done[i] = true;
        int t = to(i);
        while (!done[t]) {
          done[t] = true;
          t = to(t);
        }
        ans = p * ans % 1000000007;
      }
    printf("%I64d", ans);
  }
  return 0;
}
