There is a sorted array $[1,2,\dots,n]$ and a permutation $p_1,p_2,\dots,p_n$ . On each round, all elements move according to the permutation: the element at position $i$ moves to position $p_i$ .

After how many rounds is the array sorted again for the first time?

The first line has an integer $n$ .

The next line contains $n$ integers $p_1,p_2,\dots,p_n$ .

• $1 \le n \le 2 \cdot 10^5$

Print the number of rounds modulo $10^9+7$ .