如果原始的数列是: 1 2 3 4 5，则使用一次置换( 3 4 5 2 1 )后变为：5 4 1 2 3；如果再次使用置换( 3 4 5 2 1 )则变为：3 2 5 4 1；多次置换的结果如下：

置换

记住啊！

题目：

题目描述

$N$ 个数的全排列有 $N!$ 种，比如 $5$ 个数的排列有 $5!=120$ 种。但是，前面的置换( $3 4 5 2 1$ )我们看到，置换 $6$ 次后，数列就还原了。

显然，置换( $3 4 5 2 1$ )只能得到6个不同的排列，或称这个置换的周期是 $6$。

当$N$比较大时，周期有可能会很大！

输入格式 第一行1个正整数：$N$，范围在[1, 1000000]，表示字符串长度。 第二行：有N个整数，为 $1$ 到 $N$ 的一个全排列，表示一个置换。

输出格式

一行，1个数，表示置换的周期数。注意输出的是：

答案% $1000007$ 。

输入/输出例子1 输入：

5 5 3 2 1 4

输出：

6