Đổi chổ

View as PDF

Submit solution


Points: 0.87 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
SRM517
Problem type
Allowed languages
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:

  1. Là hoán vị của ~N - 1~ số gồm các số từ ~1~ đến ~N - 1~.
  2. 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

Please read the guidelines before commenting.



  • 0
    buivietthanh  commented on Nov. 12, 2023, 4:17 a.m.

    *Đổi chỗ