Minimum Number of Permutation Operations

Given a permutation p of 1..n. One operation simultaneously sets temp[i]=arr[p[i]] for every 1-based index i, and then sets arr=temp. For an initial array of any n distinct elements, find the minimum number of operations needed to return to the initial array, modulo 1,000,000,007.

This site adds the standard input/output protocol.

输入格式

n; the second line contains the n permutation values p[i].

输出格式

Output the minimum number of operations modulo 1,000,000,007.

样例 1

输入：

3
1 3 2

输出：

2

样例 2

输入：

4
2 1 4 3

输出：

2

样例 3

输入：

5
2 3 1 5 4

输出：

6