Giải bài trực tuyến

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 ≤ 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.

Dữ liệu

• 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.

Kết quả

• Phần dư khi chia số hoán vị đẹp cho 10⁹ + 7.

Ví dụ

Input:
4
2 0 3 1

Output:
2

Giải thích:

• 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).

Giới hạn:

1 ≤ N ≤ 100, 20% số test N ≤ 10.