#include <bits/stdc++.h>
using namespace std;
long long p, k;
const int mod = 1e9 + 7;
long long cal(long long a, long long b) {
  long long ans = 1;
  while (b > 0) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    a = (a * a) % mod;
    b /= 2;
  }
  return ans;
}
int main() {
  scanf("%I64d %I64d", &p, &k);
  if (k == 0) {
    printf("%I64d\n", cal(p, p - 1));
  } else if (k == 1) {
    printf("%I64d\n", cal(p, p));
  } else {
    long long ret = 1;
    for (long long i = k; i != 1; i = (i * k) % p) {
      ret++;
    }
    ret = (p - 1) / ret;
    printf("%I64d\n", cal(p, ret));
  }
  return 0;
}
