Giáo sư JOI là một chuyên gia hàng đầu về lịch sử Vương quốc IOI. Khi khảo sát một ngôi đền cổ trong vương quốc, ông tìm thấy một khu di tích từng có các cột đá. Ông cũng tìm thấy một tài liệu cổ được cho là do cư dân Vương quốc IOI thời xưa viết lại. Tài liệu mô tả các cột đá như sau:

• Ngay sau khi được dựng lên, có \(2N\) cột đá, được đánh số từ \(1\) đến \(2N\).
• Ngay sau khi được dựng lên, với mỗi \(k\) (\(1 \le k \le N\)), có đúng hai cột đá cao \(k\).
• Đã xảy ra \(N\) trận động đất. Sau mỗi trận, một số cột đá bị sụp một phần và chiều cao giảm đi \(1\). Những cột khác được người xưa bảo vệ nên không bị sụp và giữ nguyên chiều cao.
• Khi xảy ra động đất, với mỗi \(k\) (\(1 \le k \le N\)), người xưa bảo vệ đúng một cột đá cao \(k\). Nếu có nhiều cột cùng cao \(k\) vào thời điểm đó, cột có chỉ số lớn nhất được bảo vệ. Nói cách khác, nếu trước trận động đất cột \(i\) (\(1 \le i \le 2N\)) có chiều cao \(h_i\), thì cột \(i\) được bảo vệ khi và chỉ khi \(h_i \ge 1\) và \(h_j \ne h_i\) với mọi \(j>i\).
• Sau \(N\) trận động đất, còn lại \(N\) cột đá, tức là có đúng \(N\) cột có chiều cao ít nhất \(1\).

Giáo sư JOI cho rằng việc khôi phục chiều cao ban đầu của \(2N\) cột đá sẽ là một phát hiện lớn. Sau khi khảo sát kỹ hơn, ông xác định được các chỉ số của những cột còn lại sau \(N\) trận động đất là \(A_1,A_2,\ldots,A_N\).

Giáo sư muốn biết có bao nhiêu cách gán chiều cao ban đầu cho \(2N\) cột đá phù hợp với tài liệu cổ và thông tin đã tìm được. Là học trò của giáo sư, bạn được giao viết chương trình tính số cách đó, lấy số dư khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo dạng sau. Tất cả các giá trị đều là số nguyên.

N
A_1 ... A_N

Dữ liệu ra

In ra một dòng chứa số dư của số cách gán chiều cao ban đầu thỏa mãn yêu cầu khi chia cho \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le N \le 600\).
• \(1 \le A_i \le 2N\) với \(1 \le i \le N\).
• \(A_i < A_{i+1}\) với \(1 \le i \le N-1\).

Phân nhóm

1. (6 điểm) \(N \le 13\).
2. (52 điểm) \(N \le 60\).
3. (42 điểm) Không có ràng buộc bổ sung.

Ví dụ

3
3 4 6

5

1
1

0

10
5 8 9 13 15 16 17 18 19 20

147003663

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi thứ 2. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.