#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
const int MOD = 1000000007;
int p, k, vis[N], inv[N], Ans = 1;
int main() {
  scanf("%d%d", &p, &k);
  if (k == 0 || k == 1) {
    for (int i = 1; i < p; i++) Ans = 1ll * Ans * p % MOD;
    if (k == 1) Ans = 1ll * Ans * p % MOD;
    printf("%d\n", Ans);
    return 0;
  }
  inv[0] = 1;
  for (int i = 1; i < N; i++) inv[i] = 1ll * inv[i - 1] * k % p;
  for (int i = 1; i < p; i++)
    if (!vis[i]) {
      int cnt = 0;
      for (int j = i; !vis[j]; j = 1ll * k * j % p) vis[j] = 1, cnt++;
      if (inv[cnt] == 1) Ans = 1ll * Ans * p % MOD;
    }
  printf("%d\n", Ans);
  return 0;
}
