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?

Input

The first line has an integer $n$.

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

Output

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

Constraints

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

Example

Input:

8
5 3 2 6 4 1 8 7

Output:

4

Explanation: The array changes as follows after the rounds:

• Round 1: $[6,3,2,5,1,4,8,7]$
• Round 2: $[4,2,3,1,6,5,7,8]$
• Round 3: $[5,3,2,6,4,1,8,7]$
• Round 4: $[1,2,3,4,5,6,7,8]$