Ta nấu tổng cộng \(N\) chiếc bánh kếp: một chiếc bán kính \(1\) cm, một chiếc \(2\) cm, ..., một chiếc \(N\) cm, theo thứ tự bất kỳ. Chiếc đầu đặt lên đĩa; mỗi chiếc sau đặt lên chiếc trước, đồng tâm. Khi vừa thêm, một bánh luôn nhìn thấy từ trên. Nó chỉ bị che khi về sau có bánh bán kính lớn hơn.

Ví dụ với \(4\) bánh: nấu bán kính \(3\) trước, có một bánh thấy được; thêm bán kính \(1\), cả hai thấy được; thêm bán kính \(2\), nó che bánh \(1\) nhưng không che bánh \(3\), còn hai bánh thấy được; cuối cùng bánh \(4\) che tất cả, chỉ còn một. Trong hình, bánh tô kín là thấy được, bánh bán trong suốt là bị che.

Gọi \(V_i\) là số bánh nhìn thấy khi chồng có đúng \(i\) bánh. Ví dụ có \(V=(1,2,2,1)\). Cho \(V_1,\ldots,V_N\), có bao nhiêu trong \(N!\) thứ tự nấu tạo đúng dãy đó? In kết quả modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ gồm hai dòng: \(N\), rồi \(N\) số \(V_1,\ldots,V_N\).

Dữ liệu ra

Với mỗi bộ, in Case #x: y, với \(y\) là số thứ tự nấu hợp lệ modulo \(1000000007\).

Ràng buộc

• \(1\le T\le100\); \(1\le V_i\le i\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(2\le N\le13\).
• Test Set 2 (Hidden Verdict): \(2\le N\le10^5\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
4
1 2 2 1
3
1 1 2
3
1 1 3

Case #1: 1
Case #2: 2
Case #3: 0

Ví dụ bổ sung — Test Set 2

1
24
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

Case #1: 234141013

??? "Giải thích"
    Có $316234143225$ thứ tự nấu tạo dãy; modulo $10^9+7$ là $234141013$. Ví dụ không chạy trên lời giải nộp.

Nguồn

Google Code Jam 2021, Vòng 2, bài Hidden Pancakes.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.