#include <bits/stdc++.h>
using namespace std;
const long long oo = 1000000007;
vector<long long> G;
bool v[1000010];
long long a[1000010];
long long f[1000010];
long long p, k, i, j, ans;
void dfs(long long o, long long st) {
  v[o] = 1;
  if (!v[(o * k) % p]) {
    dfs((o * k) % p, st + 1);
  } else {
    G.push_back(st);
    a[st]++;
  }
}
int main() {
  scanf("%I64d%I64d", &p, &k);
  if (k == 0) {
    long long tem = 1;
    for (i = 1; i < p; ++i) tem = (tem * p) % oo;
    printf("%I64d\n", tem);
    return 0;
  }
  for (i = 0; i < p; ++i) {
    if (!v[i]) {
      dfs(i, 1);
    }
  }
  memset(v, 0, sizeof(v));
  for (i = 0; i < G.size(); ++i) {
    if (v[G[i]]) continue;
    v[G[i]] = 1;
    for (j = 1; j * j <= G[i]; ++j) {
      if (G[i] % j) continue;
      f[G[i]] = (f[G[i]] + a[j] * j) % oo;
      if (j * j != G[i])
        f[G[i]] = (f[G[i]] + (a[G[i] / j] * (G[i] / j)) % oo) % oo;
    }
  }
  ans = 1;
  for (i = 0; i < G.size(); ++i) {
    ans = (ans * f[G[i]]) % oo;
  }
  printf("%I64d\n", ans);
  return 0;
}
