#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int vis[8000005];
int cnt = 0;
int part = 0;
int pnt[8000005], head[8000005], nxt[8000005];
void addedge(int u, int v) {
  pnt[cnt] = v;
  nxt[cnt] = head[u];
  head[u] = cnt++;
}
void dfs(int u, int f) {
  vis[u] = 1;
  for (int i = head[u]; ~i; i = nxt[i]) {
    int v = pnt[i];
    if (v != f && !vis[v]) {
      dfs(v, u);
    }
  }
}
int main() {
  memset(head, -1, sizeof head);
  int p, k;
  cin >> p >> k;
  for (int i = 1; i < p; i++) {
    int u = i;
    int v = (long long)k * i % p;
    addedge(u, v);
    addedge(v, u);
  }
  for (int i = 1; i < p; i++) {
    if (!vis[i]) {
      part++;
      dfs(i, -1);
    }
  }
  long long sum = 1;
  if (k == 0) part = p - 1;
  if (k == 1) part = p;
  for (int i = 1; i <= part; i++) {
    sum = (sum * p) % MOD;
  }
  cout << sum << endl;
  return 0;
}
