#include <bits/stdc++.h>
using namespace std;
const int M = 1e9 + 7;
int p, k;
int g[1001000], vis[1001000];
int power(int x, int n) {
  int res = 1;
  while (n) {
    if (n & 1) res = 1ll * res * x % M;
    x = 1ll * x * x % M;
    n >>= 1;
  }
  return res;
}
void dfs(int u) {
  if (vis[u]) return;
  vis[u] = 1;
  dfs(g[u]);
}
int main() {
  scanf("%d %d", &p, &k);
  int ans = 1;
  if (k == 1) {
    ans = power(p, p);
  } else if (k == 0) {
    ans = power(p, p - 1);
  } else {
    for (int i = 1; i < p; i++) {
      int a = 1ll * k * i % p;
      int b = i;
      g[a] = b;
    }
    for (int i = 1; i < p; i++)
      if (!vis[i]) {
        dfs(i);
        ans = 1ll * ans * p % M;
      }
  }
  printf("%d\n", ans);
}
