#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
const int M = 1000010;
const int MOD = 1000000007;
const long long INF = 0x7fffffff;
const int dir4[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const int dir8[8][2] = {{-1, 0}, {-1, 1}, {0, 1},  {1, 1},
                        {1, 0},  {1, -1}, {0, -1}, {-1, -1}};
const double eps = 1e-8;
const double PI = acos(-1.0);
inline int sign(double x) { return (x > eps) - (x < -eps); }
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
inline T Min(T a, T b) {
  return a < b ? a : b;
}
template <class T>
inline T Max(T a, T b) {
  return a > b ? a : b;
}
int n, k, vis[N];
long long Mod_exp(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % c;
    a = (a % c) * (a % c) % c;
    b /= 2;
  }
  return ans;
}
int main() {
  while (scanf("%d%d", &(n), &(k)) != EOF) {
    (memset((vis), 0, sizeof(vis)));
    int r = 0;
    if (k == 0)
      r = n - 1;
    else if (k == 1)
      r = n;
    else {
      for (int i = 1; i < n; i++) {
        if (vis[i]) continue;
        r++;
        for (long long j = i; !vis[j]; j = j * k % n) vis[j] = 1;
      }
    }
    printf("%I64d\n", (Mod_exp((long long)n, (long long)r, (long long)MOD)));
  }
  return 0;
}
