#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
const long long MOD = 1000000007;
vector<int> adj[MAXN];
bool visi[MAXN];
int main() {
  ios::sync_with_stdio(false);
  ;
  long long p, k;
  cin >> p >> k;
  if (!k) {
    long long ans = 1;
    for (int i = 0; i < (p - 1); ++i) ans = (ans * p) % MOD;
    cout << ans << "\n";
    return 0;
  } else if (k == 1) {
    long long ans = 1;
    for (int i = 0; i < (p); ++i) ans = (ans * p) % MOD;
    cout << ans << "\n";
    return 0;
  }
  for (int i = 0; i < (p); ++i) {
    long long vtx = (k * i) % p;
    adj[vtx].push_back(i);
    adj[i].push_back(vtx);
  }
  long long ans = 1;
  stack<int> st;
  for (int i = 0; i < (p); ++i)
    if (!visi[i]) {
      st.push(i);
      while (!st.empty()) {
        bool found = false;
        int top = st.top();
        visi[top] = true;
        for (__typeof((adj[top]).begin()) it = (adj[top]).begin();
             it != (adj[top]).end(); ++it)
          if (!visi[*it]) {
            found = true;
            st.push(*it);
            break;
          }
        if (!found) st.pop();
      }
      if (i || !k) ans = (ans * p) % MOD;
    }
  cout << ans << "\n";
  return 0;
}
