#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int MAXN = 1010000;
const int MOD = 1000000007;
const long long INF = 1000000000LL;
char s[MAXN];
int dp[MAXN][2][3] = {0};
void checkmax(int &ans, int tmp) {
  if (tmp > ans) ans = tmp;
}
void open(char *file) {
  freopen(file, "r", stdin);
  int len = strlen(file);
  file[len] = 't';
  file[len + 1] = 0;
  file[len - 1] = 'u';
  file[len - 2] = 'o';
  freopen(file, "w", stdout);
}
void check(char s[], int n) {
  int len = strlen(s);
  assert(len == n);
  for (int i = 0; i < n; i++) {
    assert(s[i] == '0' || s[i] == '1');
  }
}
int vis[MAXN];
long long pwd[MAXN];
long long pk[MAXN];
int calc(long long s, long long k, long long p) {
  int ret = 0;
  while (!vis[s]) {
    vis[s] = true;
    ret++;
    s = k * s % p;
  }
  return ret;
}
int main() {
  char file[100] = "20.in\0iiiiiii";
  int n, m;
  int p, k;
  int i, j;
  int ioflag = 1;
  ioflag = scanf("%d%d", &p, &k);
  pwd[0] = 1;
  for (i = 1; i < MAXN; i++) pwd[i] = pwd[i - 1] * (long long)(p) % MOD;
  pk[0] = 1;
  for (i = 1; i < MAXN; i++) pk[i] = pk[i - 1] * (long long)(k) % p;
  long long ans = 1;
  if (k == 0) {
    ans = pwd[p - 1];
  } else {
    for (i = 0; i < p; i++) {
      if (!vis[i]) {
        int len = calc(i, k, p);
        if (pk[len] == 1) ans = ans * (long long)p % MOD;
      }
    }
  }
  cout << ans << endl;
  return 0;
}
