#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
const int inf = 0x3f3f3f3f;
const string debug_line = "yolo";
const double PI = 4 * atan(1);
int per[1000001];
vector<int> Adj[1000001];
bool visited[1000001];
int count1[1000001];
long long f[1000001];
int gsize = 0;
long long power(long long b, long long e) {
  if (e == 0) {
    return 1LL;
  } else if (e == 1) {
    return b;
  } else {
    long long p = power(b, e / 2);
    if (e % 2 == 0) {
      return (p * p) % 1000000007;
    } else {
      p = (p * p) % 1000000007;
      p = (p * b) % 1000000007;
      return p;
    }
  }
}
void DFS(int u, int p) {
  gsize++;
  visited[u] = true;
  for (auto &(t1) : (Adj[u])) {
    if (!visited[t1] && t1 != p) {
      DFS(t1, u);
    }
  }
}
int main() {
  long long p;
  long long k;
  scanf("%lld%lld", &p, &k);
  int n = p;
  if (k == 0) {
    printf("%lld\n", power(n, n - 1));
  } else {
    for (int(i) = (0); (i) < (n); ++(i)) {
      Adj[(k * i) % p].push_back(i);
    }
    for (int(i) = (0); (i) < (n); ++(i)) {
      if (!visited[i]) {
        gsize = 0;
        DFS(i, i);
        count1[gsize]++;
      }
    }
    long long answer1 = 1;
    answer1 = power(count1[1], count1[1]) % 1000000007;
    for (int(i) = (2); (i) < (n + 1); ++(i)) {
      if (count1[i] != 0) {
        cerr << "( "
             << "i"
             << " , "
             << "count1[i]"
             << " ) = ( " << (i) << " , " << (count1[i]) << " )\n";
        ;
        answer1 =
            (answer1 * power((count1[i] * i + 1) % 1000000007, count1[i])) %
            1000000007;
      }
    }
    printf("%lld\n", answer1);
  }
  return 0;
}
