func_code_string: #include <bits/stdc++.h>   using namespace std;   template <class T>   inline void Read(T &x) {     int f = 1;     char t = getchar();     while (t <  0  || t >  9 ) {       if (t ==  - ) f = -1;       t = getchar();     }     x = 0;     while (t >=  0  && t <=  9 ) {       x = x * 10 + t -  0 ;       t = getchar();     }     x *= f;   }   const int modulo = 1000000007;   const int maxn = 1000005;   int p, k;   int fst[maxn], v[maxn << 1], nxt[maxn << 1], e_cn;   bool flag[maxn], vis[maxn], cycle;   void addedge(int x, int y) {     e_cn++;     v[e_cn] = y, nxt[e_cn] = fst[x], fst[x] = e_cn;   }   void input() { Read(p), Read(k); }   int pwr(long long x, long long k) {     long long re = 1;     while (k > 0) {       if (k & 1) re = 1ll * re * x % modulo;       x = 1ll * x * x % modulo;       k >>= 1;     }     return re;   }   void dfs(int cn) {     vis[cn] = true;     cycle |= flag[cn];     for (register int i = fst[cn]; i; i = nxt[i]) {       if (!vis[v[i]]) {         dfs(v[i]);       }     }   }   void solve() {     if (k == 0) {       cout << pwr(p, p - 1) << endl;       return;     }     if (k == 1) {       cout << pwr(p, p) << endl;       return;     }     long long ans = 1;     for (register int i = 0; i < p; i++) {       int x = i, y = 1ll * i * k % p;       if (x == y)         flag[x] = true;       else         addedge(x, y), addedge(y, x);     }     for (register int i = 0; i < p; i++) {       if (!vis[i]) {         cycle = false;         dfs(i);         if (!cycle) ans = 1ll * ans * p % modulo;       }     }     cout << ans << endl;   }   int main() {     input();     solve();     return 0;   }   