#include <bits/stdc++.h>
using namespace std;
int par[1000009], a[1000009];
long long mod = 1000000007;
inline int parent(int pos) {
  if (par[pos] != pos) {
    par[pos] = parent(par[pos]);
  }
  return par[pos];
}
int main() {
  long long p, k;
  scanf("%lld", &p);
  scanf("%lld", &k);
  if (k == 0) {
    long long ans = 1;
    for (int i = 0; i < p - 1; i++) {
      ans = ans * p;
      ans %= mod;
    }
    printf("%lld\n", ans);
    return 0;
  }
  for (int i = 0; i <= p; i++) {
    par[i] = i;
  }
  for (long long i = 0; i < p; i++) {
    long long x = (i * k) % p;
    int p1 = parent(i);
    int p2 = parent(x);
    if (p1 != p2) {
      par[p1] = p2;
    }
  }
  for (int i = 0; i < p; i++) {
    int x = parent(i);
    a[x] = 1;
  }
  int cnt = 0;
  for (int i = 0; i < p; i++) {
    if (a[i]) {
      cnt++;
    }
  }
  if (k != 1) cnt--;
  long long ans = 1;
  for (int i = 0; i < cnt; i++) {
    ans = ans * p;
    ans %= mod;
  }
  printf("%lld\n", ans);
}
