Cycle Value Sum after Permutation Swap

Given a permutation $$A=(a_1, a_2,\ldots,a_n)$$ of length \(n\), we define its power as follows: For any integer \(k\ge 0\), define \[ A^{(k)} = \begin{cases} (i)_{{1\le i\le n}} = (1,2,\ldots,n), & k=0,\\ (a^{(k)}_1,a^{(k)}_2,\ldots,a^{(k)}_n), & k>0,\quad\text{where } a^{(k)}_i = a^{(k-1)}_{a_i}, \end{cases} \] It is easy to prove that any power of a permutation is also a permutation. The cycle value \(v(P)\) of a permutation \(P\) is defined as the smallest positive integer \(k\) such that \[ P^{(k+1)} = P. \] For the given permutation \(A\), for every pair of indices \(1\le i,j\le n\) define \[ f(i,j)=\begin{cases} 0, & \text{if there exists } k\ge 0 \text{ such that } a^{(k)}_i=j,\\ v(A_{ij}), & \text{otherwise}, \end{cases} \] where \(A_{ij}\) is the permutation obtained by swapping \(a_i\) and \(a_j\) in \(A\). In other words, if \(j\) is in the cycle of \(i\) in \(A\) then \(f(i,j)=0\); otherwise, if \(i\) and \(j\) lie in two different cycles of \(A\) and swapping them merges the two cycles, then \(f(i,j)=v(A_{ij})\). It is a known fact that swapping two elements from different cycles merges those two cycles. If the two cycles in \(A\) have lengths \(L_1\) and \(L_2\) respectively, then after swapping, the merged cycle has length \(L_1+L_2\). Let the cycle decomposition of \(A\) be \(C_1,C_2,\ldots,C_m\) with lengths \(L_1,L_2,\ldots,L_m\). Notice that apart from the merged cycle, the other cycles remain unchanged. Therefore, one may compute \[ v(A_{ij}) = \operatorname{lcm}(L_i+L_j,\,\{L_k : k\neq i,j\}), \] where \(\operatorname{lcm}\) denotes the least common multiple and for an empty set the \(\operatorname{lcm}\) is taken to be 1.

Your task is to compute, modulo \(10^9+7\), \[ S = \sum_{i=1}^{n}\sum_{j=1}^{n} f(i,j). \]

Note: In the sum, only those pairs \((i,j)\) for which \(j\) is not in the same cycle as \(i\) in \(A\) (i.e. \(f(i,j)\neq 0\)) contribute; for pairs in the same cycle, \(f(i,j)=0\).

inputFormat

The first line contains an integer \(n\) \((1\le n\le 10^5)\), the length of the permutation. The second line contains \(n\) space-separated integers \(a_1,a_2,\ldots,a_n\) which form a permutation of \(\{1,2,\ldots,n\}\).

outputFormat

Output a single integer, the value of \(S\) modulo \(10^9+7\).

sample

3
1 2 3

12