#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16777216")
const long double PI(acos(-1.0));
using namespace std;
bool u[2000000];
int main() {
  cout.precision(10);
  long long p, k, ans = 1, num = 0;
  scanf("%I64d%I64d", &p, &k);
  if (k == 0) {
    num = p - 1;
  } else {
    num += (k == 1);
    for (int i = 1; i < p; ++i) {
      if (u[i]) continue;
      u[i] = true;
      long long next = (i * k) % p;
      while (next != i) {
        u[next] = true;
        next *= k, next %= p;
      }
      ++num;
    }
  }
  for (int i = 0; i < num; i++) ans *= p, ans %= (int)(1e9 + 7);
  printf("%I64d", ans);
}
