#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T BM(T p, T e, T M) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T MDINV(T a, T M) {
  return BM(a, M - 2, M);
}
template <class T>
inline T PW(T p, T e) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p);
    p = (p * p);
  }
  return (T)ret;
}
template <class T>
string NTS(T Number) {
  stringstream ss;
  ss << Number;
  return ss.str();
}
template <class T>
T stringtonumber(const string &Text) {
  istringstream ss(Text);
  T result;
  return ss >> result ? result : 0;
}
template <class T>
bool ISLEFT(T a, T b, T c) {
  if (((a.first - b.first) * (b.second - c.second) -
       (b.first - c.first) * (a.second - b.second)) < 0.0)
    return 1;
  else
    return 0;
}
template <typename T>
T in() {
  char ch;
  T n = 0;
  bool ng = false;
  while (1) {
    ch = getchar();
    if (ch == '-') {
      ng = true;
      ch = getchar();
      break;
    }
    if (ch >= '0' && ch <= '9') break;
  }
  while (1) {
    n = n * 10 + (ch - '0');
    ch = getchar();
    if (ch < '0' || ch > '9') break;
  }
  return (ng ? -n : n);
}
long long int par[1000000 + 2];
long long int un(long long int u) {
  if (par[u] == u)
    return u;
  else
    return par[u] = un(par[u]);
}
int main() {
  long long int n, m;
  scanf("%lld%lld", &n, &m);
  for (long long int i = 0; i <= n; i++) {
    par[i] = i;
  }
  for (long long int i = 0; i < n; i++) {
    long long int x = (i * m) % n;
    long long int ok = un(x);
    long long int op = un(i);
    if (ok < op) swap(ok, op);
    if (ok != op) par[ok] = op;
  }
  long long int res = 1;
  for (long long int i = 1; i < n; i++) {
    if (un(i) == i || un(i) == 0) {
      res = (res * n) % 1000000007ll;
    }
  }
  if (m == 1) res = (res * n) % 1000000007ll;
  printf("%lld\n", res);
  return 0;
}
