#include <bits/stdc++.h>
using namespace std;
long long p, k, cur, ord;
long long power(long long a, long long b) {
  if (b == 0) return 1ll;
  if (b == 1) return a % 1000000007;
  if (b % 2)
    return power(a, b / 2) * power(a, b / 2) % 1000000007 * a % 1000000007;
  return power(a, b / 2) * power(a, b / 2) % 1000000007;
}
int main() {
  scanf("%I64d %I64d", &p, &k);
  if (k == 0)
    printf("%I64d\n", power(p, p - 1));
  else if (k == 1)
    printf("%I64d\n", power(p, p));
  else {
    ord = 1, cur = k;
    for (; cur != 1; ord++) cur = cur * k % p;
    printf("%I64d\n", power(p, (p - 1) / ord));
  }
  return 0;
}
