No.590 Replacement
Problem Statement
MAK and culcul came up with the following game.
This game requires $2$ permutations $A,B$ of $(1,2,\dots ,N)$. The permutations $A,B$ are 1-indexed. Initially, MAK and culcul each hold $1$ natural number between $1$ and $N$, inclusive, and they perform the following operation until the values of the natural numbers held by the $2$ of them become equal. Note that there may be cases where, no matter how many times the operation is repeated, the values held by the $2$ of them never become equal and the game does not end.
・ If MAK holds a natural number $i$, then $i$ is converted to the natural number $A_i$. Likewise, if culcul holds a natural number $j$, then $j$ is converted to the natural number $B_j$.
These $2$ conversions are performed simultaneously.
To learn about the properties of this game, MAK and culcul defined a function $f(x,y)$ as follows. (Refer to Sample $1$.)
$\begin{eqnarray}\ f(x,y)=\begin{cases} 最初、MAK君が自然数x、culcul君が自然数yを持っていた時、遊びが終了するまでに操作を行った回数 &(遊びが終了する場合) \\
0 &(遊びが終了しない場合) \end{cases}\end{eqnarray}$
MAK and culcul became curious about the value of the sum of $f(i,j)$ over $1\le i,j\le N$, that is, $\displaystyle \sum_{i=1}^{N}\displaystyle \sum_{j=1}^{N}f(i,j)$. Since this value can be very large, output the remainder when it is divided by $10^9+7=1{,}000{,}000{,}007$.
Input
$N$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$
$1\le N\le 10^5$
$1\le A_i,B_i \le N$ $(1\le i\le N)$
If $i\neq j$, then $A_i\neq A_j,B_i\neq B_j$
Output
Output the remainder when $\displaystyle \sum_{i=1}^{N}\displaystyle \sum_{j=1}^{N}f(i,j)$ is divided by $1{,}000{,}000{,}007$. Print a newline at the end.
Sample
Sample 1
Input
4 2 1 4 3 3 1 2 4
Output
26
If MAK initially holds $2$ and culcul initially holds $1$, then after performing the operation $2$ times, both MAK and culcul hold $2$, and the game ends. Therefore, $f(2,1)=2$.
If MAK holds $2$ and culcul holds $4$, the game never ends no matter how many times the operation is performed, so $f(2,4)=0$.
Also, if MAK holds $1$ and culcul holds $1$, the game ends without performing any operation, so $f(1,1)=0$.
Sample 2
Input
5 1 2 3 4 5 1 2 3 4 5
Output
0
The value to output may be $0$.
Sample 3
Input
6 6 2 1 4 3 5 2 4 5 1 3 6
Output
81
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Pulmn
ixmel