#include <bits/stdc++.h>
using namespace std;
const int maxint = -1u >> 1;
const long long MOD = 1000000007LL;
const int maxn = 1000000 + 100;
bool vis[maxn];
long long mpow(long long a, int b, long long mod) {
  if (a == 0LL) return 0LL;
  long long ans = 1LL;
  long long base = a;
  while (b != 0) {
    if (b & 1) {
      ans = (ans * base) % mod;
    }
    base = (base * base) % mod;
    b >>= 1;
  }
  return ans;
}
long long solve(long long n, long long x) {
  memset(vis, false, sizeof(vis));
  int cnt = 0;
  for (int i = 1; i < (int)n; i++) {
    if (vis[i]) continue;
    cnt++;
    vis[i] = true;
    long long tmp = ((long long)i * x) % n;
    while (!vis[(int)tmp]) {
      vis[(int)tmp] = true;
      tmp = (tmp * x) % n;
    }
  }
  if (x == 1LL) cnt++;
  return mpow(n, cnt, MOD);
}
int p, k;
int main() {
  ios::sync_with_stdio(false);
  while (cin >> p >> k) {
    cout << solve((long long)p, (long long)k) << endl;
  }
  return 0;
}
