Count Operations

You are given a 1-based permutation p. One operation sets item i of the new array to item p[i] of the old array. For any array of distinct elements, find the number of repeated operations needed to restore the original array for the first time (at least one operation), modulo 1,000,000,007.

输入格式

The first line contains n; the second line contains n integers p[i]. Source constraints: 1≤n≤100000, and p is a permutation of 1..n.

输出格式

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

样例 1

输入：

1
1

输出：

1

样例 2

输入：

2
2 1

输出：

2

样例 3

输入：

3
2 3 1

输出：

3