#include <bits/stdc++.h>
using namespace std;
bool vis[1000005];
int father[1000005];
long long quick_power(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y & 1) res = res * x % 1000000007;
    x = x * x % 1000000007;
    y >>= 1;
  }
  return res;
}
int all;
int find(int x) {
  if (father[x] == x) return x;
  father[x] = find(father[x]);
  return father[x];
}
int main() {
  int k, p;
  scanf("%d%d", &p, &k);
  long long ans;
  if (k == 0) {
    ans = quick_power(p, p - 1);
  } else if (k == 1) {
    ans = quick_power(p, p);
  } else {
    for (int i = 0; i < p; ++i) {
      father[i] = i;
    }
    for (int i = 0; i < p; ++i) {
      long long s = (long long)k * (long long)i % p;
      if (i == 41195) {
        i = i + 1 - 1;
      }
      int x = find(s), y = find(i);
      father[x] = y;
    }
    int cnt = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < p; ++i) {
      int x = find(i);
      if (!vis[x]) {
        ++cnt;
        vis[x] = true;
      }
    }
    ans = quick_power(p, cnt - 1);
  }
  printf("%I64d\n", ans);
}
