Đổi chổ
Xem dạng PDF
Gửi bài giải
Điểm:
0,87 (OI)
Giới hạn thời gian:
0.38s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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)~.
Bình luận
*Đổi chỗ