#include <bits/stdc++.h>
using namespace std;
const long long BP = 1e9 + 7;
long long expo(long long a, long long n) {
  if (n == 0) return 1;
  if (n < 0) return expo(a, BP + n - 1);
  long long x = expo(a, n / 2);
  if (n & 1) return (((x * x) % BP) * a) % BP;
  return (x * x) % BP;
}
int ordre(int k, int p) {
  long long x = k;
  x %= p;
  int m = 1;
  while (x != 1) {
    x *= (long long)k;
    x %= p;
    m++;
  }
  return m;
}
int main() {
  int p, k;
  scanf("%d%d", &p, &k);
  if (k == 0) {
    printf("%lld\n", expo(p, p - 1));
  } else if (k == 1) {
    printf("%lld\n", expo(p, p));
  } else {
    printf("%lld\n", expo(p, (p - 1) / ordre(k, p)));
  }
}
