#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
long long mod = 1e9 + 7;
long long p, k, vis[N];
void dfs(long long x) {
  vis[x] = 1;
  long long f = (k * x) % p;
  if (!vis[f]) dfs(f);
}
long long exp(long long b, long long e, long long M) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = (ans * b) % M;
    b = (b * b) % M;
    e /= 2;
  }
  return ans;
}
int main() {
  scanf("%lld %lld", &p, &k);
  ;
  long long ans = 1, mul;
  for (int i = 1; i <= p - 1; i++) {
    if (!vis[i]) {
      dfs(i);
      ans = (ans * p) % mod;
    }
  }
  if (k == 1) ans = (ans * p) % mod;
  printf("%lld\n", ans);
}
