#include <bits/stdc++.h>
using namespace std;
int Ans = 1, p, k, num[1000010];
bool visit[1000010];
void dfs(int x, int depth) {
  visit[x] = true;
  x = (1ll * x * k) % p;
  if (visit[x]) {
    num[depth]++;
    return;
  }
  dfs(x, depth + 1);
}
int ksm(int x, int y) {
  int ret = 1;
  while (y > 0) {
    if (y % 2 == 1) ret = (1ll * ret * x) % 1000000007;
    x = (1ll * x * x) % 1000000007;
    y = y / 2;
  }
  return ret;
}
void work() {
  cout << ksm(p, p - 1);
  exit(0);
}
int main() {
  scanf("%d%d", &p, &k);
  if (k == 0) work();
  memset(visit, false, sizeof(visit));
  for (int i = 1; i <= p - 1; i++)
    if (!visit[i]) dfs(i, 1);
  Ans = Ans * (num[1] + 1) % 1000000007;
  for (int i = 1; i <= p - 1; i++)
    for (int j = 1; j <= num[i]; j++)
      Ans = (1ll * Ans * (num[i] * i + 1ll)) % 1000000007;
  cout << Ans;
}
