#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int p, k;
int was[1200000];
int cnt;
int main() {
  scanf("%d%d", &p, &k);
  if (k == 0) {
    long long ans = 1;
    for (int i = 0; i < p - 1; ++i) ans = (ans * p) % MOD;
    cout << ans << "\n";
    return 0;
  }
  if (k != 1) was[0] = 1;
  for (int i = 0; i < p; ++i) {
    if (was[i]) continue;
    ++cnt;
    long long now = i;
    while (!was[now]) {
      was[now] = 1;
      now = (now * k) % p;
    }
  }
  long long ans = 1;
  for (int i = 0; i < cnt; ++i) ans = (ans * p) % MOD;
  cout << ans << "\n";
  return 0;
}
