#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000001;
const int MOD = 1000000007;
int p, k, vis[maxn];
long long mypow(long long a, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res = res * a % MOD;
    n >>= 1;
    a = a * a % MOD;
  }
  return res;
}
long long run() {
  if (!k) return mypow(p, p - 1);
  if (k == 1) return mypow(p, p);
  long long cnt = 1, t = k;
  while (t != 1) t = t * k % p, cnt++;
  return mypow(p, (p - 1) / cnt);
}
int main() {
  scanf("%d%d", &p, &k);
  printf("%I64d\n", run());
  return 0;
}
