#include <bits/stdc++.h>
using namespace std;
long long k, k1, p, res = 1, base = 1000000007, t = 100;
bool mark[1000001];
int Q[1000001];
long long power(long long a, long long n, long long mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * a) % mod;
    n >>= 1;
    a = (a * a) % mod;
  }
  return res;
}
void bfs(long long x) {
  int first = 0, last = 1;
  Q[0] = x;
  mark[x] = 1;
  while (first < last) {
    x = Q[first++];
    int y = x * k % p, z = x * k1 % p;
    if (!mark[y]) Q[last++] = y;
    if (!mark[z]) Q[last++] = z;
    mark[y] = mark[z] = 1;
  }
}
int main() {
  cin >> p >> k;
  if (k == 0) {
    cout << power(p, p - 1, base);
    return 0;
  }
  if (k == 1) {
    cout << power(p, p, base);
    return 0;
  }
  k1 = power(k, p - 2, p);
  mark[0] = 1;
  for (long long x = 1; x < p; x++)
    if (!mark[x]) {
      bfs(x);
      res = (res * p) % base;
    }
  cout << res;
}
