C11SWAP - Đổi chổ

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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 9 + 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.

  • Người up: yenthanh132
  • Nguồn bài: SRM517