Vào năm 2XXX, các quốc gia trên thế giới nằm trên một đường thẳng. Có \(N\) quốc gia, được đánh số \(1,2,\ldots,N\). Với mỗi \(i=1,2,\ldots,N-1\), quốc gia \(i\) và quốc gia \(i+1\) là hai nước láng giềng.

Tại kỳ Olympic Tin học Quốc tế năm đó, quốc gia \(i\) có \(A_i\) thí sinh tham dự. Bạn là thành viên ban kỹ thuật, phụ trách lập sơ đồ chỗ ngồi cho các thí sinh. Do phòng thi dài và hẹp, các thí sinh phải được xếp vào \(A_1+A_2+\cdots+A_N\) chỗ ngồi trên một hàng.

Để ngăn ngừa gian lận, hai thí sinh đến từ cùng một quốc gia hoặc từ hai quốc gia láng giềng không được ngồi cạnh nhau. Các thí sinh là những người phân biệt, kể cả khi họ đến từ cùng một quốc gia.

Có bao nhiêu cách xếp các thí sinh vào các chỗ ngồi? Vì kết quả có thể rất lớn, hãy tìm phần dư của số cách khi chia cho \(10007\).

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau:

N
A_1 A_2 ... A_N

Dữ liệu ra

In ra một dòng chứa số cách xếp chỗ ngồi thỏa mãn điều kiện, lấy phần dư khi chia cho \(10007\).

Ràng buộc

• Các giá trị đầu vào đều là số nguyên.
• \(1 \le N \le 100\).
• \(1 \le A_i \le 4\) với \(1 \le i \le N\).

Phân nhóm

1. Nhóm 1 (6 điểm): \(1 \le N \le 5\) và \(1 \le A_i \le 2\) với mọi \(1 \le i \le N\).
2. Nhóm 2 (14 điểm): \(1 \le N \le 10\) và \(1 \le A_i \le 3\) với mọi \(1 \le i \le N\).
3. Nhóm 3 (80 điểm): \(1 \le N \le 100\) và \(1 \le A_i \le 4\) với mọi \(1 \le i \le N\).

Ví dụ

4
2 1 1 1

4

5
1 2 3 2 1

0

6
1 2 3 3 2 1

4754

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật, đối chiếu với bản trên AtCoder, của Ủy ban Olympic Tin học Nhật Bản, vòng loại JOI 2018/2019. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.