#include <bits/stdc++.h>
const int INF = 1e9;
const long long lINF = 1e18;
const double EPS = 1e-12;
using namespace std;
const int MOD = (int)1e9 + 7;
int mult(int a, int b, int m) { return (long long)a * b % m; }
int power(int a, int p, int m) {
  int ans = 1;
  while (p) {
    if (p & 1) {
      ans = mult(ans, a, m);
    }
    p >>= 1;
    a = mult(a, a, m);
  }
  return ans;
}
int main() {
  int p, k;
  scanf("%d%d", &p, &k);
  int ans = 1;
  if (k == 0) {
    ans = mult(ans, power(p, p - 1, MOD), MOD);
  }
  if (k > 0) {
    int mn = -1;
    for (int cur = k, i = 1;; i++) {
      if (cur == 1) {
        mn = i;
        break;
      }
      cur = mult(cur, k, p);
    }
    ans = mult(ans, power(p, (p - 1) / mn, MOD), MOD);
  }
  if (k == 1) {
    ans = mult(ans, p, MOD);
  }
  printf("%d\n", ans);
  return 0;
}
