#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
bool vis[1000005];
int main() {
  long long p, k;
  scanf("%lld%lld", &p, &k);
  long long ans = 1;
  for (int i = 1; i < p; i++) {
    if (vis[i] == 0) {
      long long ii = i;
      if (vis[ii] == 0) {
        ans = ans * p % mod;
      }
      while (1) {
        if (vis[ii] == 0) {
          vis[ii] = 1;
        } else
          break;
        ii = (ii * k) % p;
      }
    }
  }
  if (k == 1) ans = ans * p % mod;
  printf("%lld\n", ans);
}
