「AHOI2022」排列

题目描述

对于一个长度为 $n$ 的排列 $P = (p_1, p_2, \ldots, p_n)$ 和整数 $k \ge 0$，定义 $P$ 的 $k$ 次幂

$$P^{(k)} = \left( p^{(k)}_1, p^{(k)}_2, \ldots, p^{(k)}_n \right), $$

该排列的第 $i$ 项为

$$p^{(k)}_i = \begin{cases} i, & k = 0, \\ p^{(k - 1)}_{p_i}, & k > 0. \end{cases} $$

容易证明任意排列的任意次幂都是一个排列。

定义排列 $P$ 的循环值 $v(P)$ 为最小的正整数 $k$ 使得 $P^{(k + 1)} = P$。

给出一个长度为 $n$ 的排列 $A = (a_1, a_2, \ldots, a_n)$，对于整数 $1 \le i, j \le n$，定义 $f(i, j)$：若存在 $k \ge 0$ 使得 $a^{(k)}_i = j$，则 $f(i, j) = 0$，否则设排列 $A_{i j}$ 为将排列 $A$ 的第 $i$ 项 $a_i$ 和第 $j$ 项 $a_j$ 交换后得到的排列，则 $f(i, j) = v(A_{i j})$。

求

$$\sum_{i = 1}^{n} \sum_{j = 1}^{n} f(i, j)$$

的值。答案可能很大，你只需要输出其对 $10^9 + 7$ 取模的结果。

输入格式

本题有多组测试数据。输入数据的第一行为一个整数 $T$，表示测试数据组数。

对于每组测试数据，第一行一个正整数 $n$ 表示排列的长度，接下来一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，描述输入的排列。

输出格式

对于每组数据输出一行一个整数，表示题目所求的答案对 $10^9 + 7$ 取模的结果。

样例 1

输入

2
3
1 2 3
3
2 3 1

输出

12
0

对于第一组测试数据，$f(1, 2) = f(2, 1) = f(2, 3) = f(3, 2) = f(1, 3) = f(3, 1) = 2$，其余的 $f(i, j)$ 均为 $0$。

对于第二组测试数据，所有的 $f(i, j)$ 均为 $0$。

样例 2

见附加文件下的 perm2.in 与 perm2.ans。

该组样例中，第一个测试数据满足 $n \le 35$，前四个测试数据满足 $n \le 200$，所有测试数据满足 $n \le 2500$。

样例 3

见附加文件下的 perm3.in 与 perm3.ans。

该组样例中，第一个测试数据满足特殊性质 A，第二个测试数据满足特殊性质 B，第三个测试数据满足特殊性质 C，前四个测试数据满足 $n \le 10^5$，第五个测试数据满足 $n \le 5 \times 10^5$。

数据范围与提示

对于 $100\%$ 的测试数据，$1 \le T \le 5$，$1 \le n \le 5 \times 10^5$，$1 \le a_i \le n$。

测试点编号	$n \le$	特殊性质
1 ~ 2	$10^5$	A
3	35	无
4	200
5	2500
6	$10^5$	B
7		C
8		无
9 ~ 10	$5 \times 10^5$

特殊性质 A：$a_i = (i \bmod n) + 1$。

特殊性质 B：对于任意 $1 \le i \le n$，存在 $1 \le k \le 20$，$a^{(k)}_i = i$。

特殊性质 C：存在大小不超过 $10$ 的集合 $S$，使得对于任意 $1 \le i \le n$，存在 $x \in S, k \ge 0$，$a^{(k)}_x = i$。

输入数据规模较大，请使用较为快速的输入方式。