#include <bits/stdc++.h>
const int p = 1000000007;
bool b[1200000];
int i, j, m, n, s;
inline int power(int x, int y) {
  if (!y) return 1;
  int t = power(x, y / 2);
  t = 1LL * t * t % p;
  if (y & 1) t = 1LL * t * x % p;
  return t;
}
int main() {
  scanf("%d%d", &n, &m);
  if (m == 1) {
    printf("%d", power(n, n));
    return 0;
  }
  for (i = 1; i < n; i++)
    if (!b[i]) {
      s++;
      for (j = i; !b[j]; j = 1LL * j * m % n) b[j] = true;
    }
  printf("%d", power(n, s));
  return 0;
}
