Pinely Round 2 (Div. 1 + Div. 2) |
---|
Finished |
You are given an array of integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$). You can perform the following operation several (possibly, zero) times:
How many distinct arrays is it possible to attain? Output the answer modulo $$$(10^9 + 7)$$$.
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 the number of attainable arrays modulo $$$(10^9 + 7)$$$.
31 1 2
2
42 1 4 3
4
62 3 1 1 1 2
18
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.
Name |
---|