Problem Description

For a permutation $P = (p_1, p_2, \ldots, p_n)$ of length $n$ and an integer $k \ge 0$, define the $k$-th power of $P$ as

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

where the $i$-th element of this permutation is

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

It is easy to prove that any power of any permutation is still a permutation.

Define the cycle value $v(P)$ of a permutation $P$ as the smallest positive integer $k$ such that $P^{(k + 1)} = P$.

Given a permutation $A = (a_1, a_2, \ldots, a_n)$ of length $n$, for integers $1 \le i, j \le n$, define $f(i, j)$ as follows: if there exists $k \ge 0$ such that $a^{(k)}_i = j$, then $f(i, j) = 0$; otherwise, let the permutation $A_{i j}$ be the permutation obtained by swapping the $i$-th element $a_i$ and the $j$-th element $a_j$ in $A$, and set $f(i, j) = v(A_{i j})$.

Compute the value of $\sum_{i = 1}^{n} \sum_{j = 1}^{n} f(i, j)$. The answer may be very large; you only need to output it modulo $({10}^9 + 7)$.

Input Format

This problem has multiple test cases. The first line contains an integer $T$, indicating the number of test cases.

For each test case, the first line contains a positive integer $n$, representing the length of the permutation. The next line contains $n$ integers $a_1, a_2, \ldots, a_n$, describing the given permutation.

Output Format

For each test case, output one line with one integer, representing the required answer modulo $({10}^9 + 7)$.

2
3
1 2 3
3
2 3 1

12
0

Hint

Sample Explanation #1

For the first test case, $f(1, 2) = f(2, 1) = f(2, 3) = f(3, 2) = f(1, 3) = f(3, 1) = 2$, and all other $f(i, j)$ are $0$.

For the second test case, all $f(i, j)$ are $0$.

Sample #2

See perm/perm2.in and perm/perm2.ans in the attachments.

In this sample, the first test case satisfies $n \le 35$, the first four test cases satisfy $n \le 200$, and all test cases satisfy $n \le 2500$.

Sample #3

See perm/perm3.in and perm/perm3.ans in the attachments.

In this sample, the first test case satisfies Special Property A, the second test case satisfies Special Property B, and the third test case satisfies Special Property C. The first four test cases satisfy $n \le {10}^5$, and the fifth test case satisfies $n \le 5 \times {10}^5$.

For the exact definitions of the special properties, see the Constraints section.

Constraints

For $100\%$ of the testdata, $1 \le T \le 5$, $1 \le n \le 5 \times {10}^5$, $1 \le a_i \le n$.

Test Point ID	$n \le$	Special Property
$1 \sim 2$	${10}^5$	A
$3$	$35$	None
$4$	$200$
$5$	$2500$
$6$	${10}^5$	B
$7$		C
$8$		None
$9 \sim 10$	$5 \times {10}^5$

Special Property A: $a_i = (i \bmod n) + 1$.
Special Property B: For any $1 \le i \le n$, there exists $1 \le k \le 20$ such that $a^{(k)}_i = i$.
Special Property C: There exists a set $S$ of size at most $10$ such that for any $1 \le i \le n$, there exist $x \in S, k \ge 0$ such that $a^{(k)}_x = i$.

Hint

The input size is large, so please use a relatively fast input method.

Translated by ChatGPT 5