Statement
对于一个长度为 \(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)\) 取模的结果。
对于 \(100 \%\) 的测试数据，\(1 \le T \le 5\)，\(1 \le n \le 5 \times {10}^5\)，\(1 \le a_i \le n\)。