#include <bits/stdc++.h>
using namespace std;
const int Mod = 1000000007;
const int Maxn = 1010101;
long long p, k, Ans;
bool visited[Maxn];
void dfs(long long v) {
  visited[v] = true;
  if (!visited[v * k % p]) dfs(v * k % p);
}
int main() {
  cin >> p >> k;
  Ans = 1;
  if (k == 1) Ans = p;
  for (int i = 1; i < p; i++) {
    if (!visited[i]) {
      dfs(i);
      Ans = Ans * p % Mod;
    }
  }
  cout << Ans << endl;
  return 0;
}
