Permutation Operations

You are given a permutation p of 1..n. Repeatedly perform the operation where item i of the new array takes item p[i] of the old array. Find the minimum number of operations needed for any array of distinct elements to return to its original state, modulo 10^9+7.

The constraints are complete; the direction in which the permutation is applied does not affect the cycle lengths or the answer.

This site adds the standard input/output protocol.

输入格式

The first line contains n (1 ≤ n ≤ 100000), and the second line contains the n numbers of p, a permutation of 1..n.

输出格式

Output the minimum positive number of operations needed to restore the original array, modulo 1000000007.

样例 1

输入：

3
2 1 3

输出：

2

样例 2

输入：

4
2 3 1 4

输出：

3

样例 3

输入：

5
2 1 4 5 3

输出：

6