#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:160777216")
using namespace std;
long long MOD = 1000000007;
int i, j, n, m;
long long k, p;
int a[2000000], u[2000000];
int sum = 0;
void solve(vector<int> v, int k, int p) {
  int i, j;
  if (v.size() < p) {
    for (i = 0; i < p; i++) {
      v.push_back(i);
      solve(v, k, p);
      v.pop_back();
    }
  } else {
    int good = 1;
    for (int x = 0; x < p; x++) {
      if ((k * v[x]) % p != v[(k * x) % p]) {
        good = 0;
        break;
      }
    }
    if (good) sum++;
  }
}
int main() {
  cin >> p >> k;
  for (long long x = 1; x < p; x++) {
    long long y = (k * x) % p;
    a[x] = y;
  }
  int cikl = 0;
  for (i = 1; i < p; i++) {
    if (!u[i]) {
      cikl++;
      int tmp = i;
      while (!u[tmp]) {
        u[tmp] = 1;
        tmp = a[tmp];
      }
    }
  }
  long long ans = 1;
  for (i = 0; i < cikl; i++) {
    ans = ans * p % MOD;
  }
  if (k == 1) ans = ans * p % MOD;
  cout << ans << endl;
  vector<int> v;
  return 0;
}
