Submit solution
Points:
0.87 (partial)
Time limit:
0.38s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho dãy số ~A~ gồm ~N~ phần tử là hoán vị của ~N~ số nguyên từ ~0~ đến ~N - 1~ và được đánh số lần lượt từ ~1~ đến ~N~. Phép biến đổi ~Swap(x)~ sẽ đổi chỗ ~A_{x}~ và ~A_{x + 1}~ ~(1 \leq x < N)~. Một hoán vị ~B~ gọi là đẹp nếu thỏa mãn ~2~ điều kiện sau:
- Là hoán vị của ~N - 1~ số gồm các số từ ~1~ đến ~N - 1~.
- Sau khi thực hiện lần lượt các phép biến đổi ~Swap(B_{1})~, ~Swap(B_{2})~, ..., ~Swap(B_{N - 1})~ trên dãy số ~A~ đã cho thì được dãy số mới là dãy tăng dần.
Yêu cầu: Hãy đếm số hoán vị đẹp.
Input
- Dòng ~1~: Số nguyên dương ~N~.
- Dòng ~2~: Gồm ~N~ số nguyên, là giá trị ban đầu của dãy số ~A~.
Output
- Phần dư khi chia số hoán vị đẹp cho ~10^{9} + 7~.
Giới hạn
~1 \leq N \leq 100~
~20\%~ số test ~N \leq 10~.
Sample Input
4
2 0 3 1
Sample Output
2
Note
- Dãy số ~A~ ban đầu là ~(2, 0, 3, 1)~.
- Các hoán vị được sinh ra là ~(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)~.
- Có ~2~ hoán vị đẹp là ~(1, 3, 2)~ và ~(3, 1, 2)~.
Comments