#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 100010;
const long long MOD = 1e9 + 7;
long long P, K;
long long calc(long long, long long);
int main() {
  scanf("%lld%lld", &P, &K);
  if (K == 0) {
    printf("%lld", calc(P, P - 1) % MOD);
    return 0;
  } else if (K == 1) {
    printf("%lld", calc(P, P) % MOD);
  } else {
    long long len = 1, now = K;
    while (now != 1) {
      now = now * K % P;
      len++;
    }
    printf("%lld", calc(P, (P - 1) / len));
  }
  return 0;
}
long long calc(long long n, long long tim) {
  long long ret = 1;
  while (tim) {
    if (tim & 1) {
      ret = ret * n % MOD;
    }
    n = n * n % MOD;
    tim >>= 1;
  }
  return ret;
}
