Score : 1400 points
You are given an integer sequence a of length N. How many permutations p of the integers 1 through N satisfy the following condition?
Find the count modulo 10^9 + 7.
The input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Print the number of the permutations p that satisfy the condition, modulo 10^9 + 7.
3 1 2 3
4
The following four permutations satisfy the condition:
For example, (1, 3, 2) satisfies the condition because p_1 = 1, p_{p_2} = 2 and p_{p_3} = 3.
2 1 1
1
The following one permutation satisfies the condition:
3 2 1 1
2
The following two permutations satisfy the condition:
3 1 1 1
0
13 2 1 4 3 6 7 5 9 10 8 8 9 11
6