A permutation of is an array of integers such that each integer from to appears exactly once in . A transformation to is defined as changing into another permutation where for all .
You are given a permutation . Your task in this problem is to count the number of distinct permutations you can get by doing a transformation to the given permutation for zero or more times.
For example, let .
By doing a transformation, you will change into .
By doing another transformation, you will change into .
By doing another transformation, you will change into again.
Therefore, there are distinct permutations you can get by doing a transformation for zero or more times.
输入格式
Input begins with a line containing an integer: () representing the number of elements in the given permutation. The next line contains integers: () representing the permutation. The elements in are guaranteed to be unique.
输出格式
Output in a line an integer representing the number of distinct permutations you can get by doing a transformation to the given permutation for zero or more times, modulo .
样例
样例输入 1
5
3 5 1 2 4
样例输出 1
3
样例输入 2
8
7 5 1 6 8 2 3 4
样例输出 2
4
数据范围与提示
Explanation for the sample input/output #1
This is the example from the problem description.
Explanation for the sample input/output #2
There are distinct permutations you can get by doing a transformation to the given permutation for zero or more times.
