#include <bits/stdc++.h>
using namespace std;
long long p, k;
bool visited[1000000];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> p >> k;
  long long ans = 1;
  if (k == 0) {
    for (int i = 0; i < (int)(p - 1); i++) {
      ans = ans * p % 1000000007;
    }
  } else if (k == 1) {
    for (int i = 0; i < (int)(p); i++) {
      ans = ans * p % 1000000007;
    }
  } else {
    for (int i = 1; i < p; i++) {
      long long x = i;
      if (!visited[x]) {
        while (!visited[x]) {
          visited[x] = true;
          x = k * x % p;
        }
        ans = ans * p % 1000000007;
      }
    }
  }
  cout << ans << endl;
  return 0;
}
