Permutation Rounds

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]