\(n\) 是质数，所以 \(a_{(xi+y)\bmod{n}}\) 是 \(a\) 的一个置换。这 \(n(n-1)\) 种置换构成一个群，而满足条件的 \(a\) 相当于是所在轨道中字典序最小的序列，因此题目转化为求轨道个数。
设 \(g(x,y)\) 为对应置换的不动点个数，由 Burnside 引理，所求即为
设满足 \(p_i=(xi+y)\bmod{n}\) 的排列 \(p\) 有 \(c(x,y)\) 个置换环，同一个置换环内必须填同一种数，于是 \(g(x,y)=m^{c(x,y)}\)。
考虑如何求出 \(c(x,y)\)。
若 \(x=1,y=0\)，则 \(c(x,y)=n\)。
若 \(x=1,y\neq 0\)，设从 \(i\) 出发走 \(k\) 步会回到 \(i\)，则 \(ky\equiv 0\pmod{n}\)，显然满足条件的最小正整数为 \(k=n\)，因此 \(c(x,y)=1\)。
若 \(x\neq 1\)，考虑 \(t\equiv xt+y\pmod{n}\) 有唯一解。对于任意的 \(i\)，将其表示成 \(i=t+j\)，则 \(x(t+j)+y\equiv t+xj\pmod{n}\)，因此该置换实际上和 \(y=0\) 对应的置换同构。对于 \(i=0\)，显然 \(xi=0\)，这会贡献一个置换环；对于 \(i\neq 0\)，还是设从 \(i\) 出发走 \(k\) 步会回到 \(i\)，则 \(x^k\equiv 1\pmod{n}\)，因此环长为 \(\operatorname{ord}_n(x)\)。加起来得到 \(c(x,y)=1+\dfrac{n-1}{\operatorname{ord}_n(x)}\)。根据经典结论，对于任意的 \(d\mid(n-1)\)，恰好有 \(\varphi(d)\) 个元素的阶为 \(d\)。
综上，答案为
对 \(n-1\) 做质因数分解，DFS 枚举约数的同时维护 \(\varphi\) 的值即可。时间复杂度为 \(\mathcal{O}(\sqrt{n}+\tau(n-1)\log{n})\)。
主要代码
int tc, p, n, m;
vector<pii> vec;
mint sum;mint qpow(mint a, ll b) {mint res = 1;for (; b; b >>= 1) {if (b & 1) res *= a;a *= a;}return res;
}void fac(int n) {vec.clear();for (int d = 2; (ll)d * d <= n; ++d) {if (n % d) continue;int cnt = 0;while (n % d == 0) {n /= d;++cnt;}vec.emplace_back(d, cnt);}if (n > 1) vec.emplace_back(n, 1);
}void dfs(int x, int d, int phi) {if (x == vec.size()) {if (d != 1) sum += phi * qpow(m, (n - 1) / d + 1);return;}auto [pr, cnt] = vec[x];int pw = 1, ph = 1;for (int i = 0; i <= cnt; ++i) {dfs(x + 1, d * pw, phi * ph);if (i == cnt) break;pw *= pr;ph = !i ? pr - 1 : ph * pr;}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> tc >> p;mint::setMod(p);while (tc--) {cin >> n >> m;fac(n - 1);sum = 0;dfs(0, 1, 1);cout << (qpow(m, n) + mint(n - 1) * m + n * sum) / (mint(n) * (n - 1)) << '\n';}return 0;
}