#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int INF = (1 << 30) - 1;
const long long mod = 1e9 + 7;
int p, k;
int vis[1000010];
int main() {
  scanf("%d%d", &p, &k);
  long long L = 0, v = 1;
  while (1) {
    if (vis[v] == 1) break;
    vis[v] = 1;
    v = 1ll * v * k % p;
    L++;
  }
  if (k == 0) L = 1;
  int y = (p - 1) / L;
  if (k == 1) y = p;
  long long ans = 1;
  for (int i = 1; i <= y; ++i) {
    ans = ans * p % mod;
  }
  printf("%I64d\n", ans);
  return 0;
}
