Swaps

Description:

Input:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1\le a_i\le n$$$).

Output:

Output the number of attainable arrays modulo $$$(10^9 + 7)$$$.

Sample Input:

3
1 1 2

Sample Output:

2

Sample Input:

4
2 1 4 3

Sample Output:

4

Sample Input:

6
2 3 1 1 1 2

Sample Output:

18

Note:

In the first example, the initial array is $$$[1, 1, 2]$$$. If we perform the operation with $$$i = 3$$$, we swap $$$a_3$$$ and $$$a_2$$$, obtaining $$$[1, 2, 1]$$$. One can show that there are no other attainable arrays.

In the second example, the four attainable arrays are $$$[2, 1, 4, 3]$$$, $$$[1, 2, 4, 3]$$$, $$$[1, 2, 3, 4]$$$, $$$[2, 1, 3, 4]$$$. One can show that there are no other attainable arrays.