Final Group Photo

Time limit1sMemory limit128 MB

Summary
Count the ways to fill a decreasing-width staircase of rows (back rows longer) with distinct heights so rows decrease left to right and columns decrease from back to front, essentially counting standard Young tableaux for a skew shape.
Level

Hard8 of 10

Topics
Combinatorics, Math, Dynamic programming
Solved
No attempts yet

Problem

A group of students with distinct heights will stand in several left-aligned rows for a group photo. The number of students in each front row is at most the number of students in the row directly behind it.

Everyone must be visible in the photo. Therefore, within each row, heights must strictly decrease from left to right. For positions in the same column, heights must also strictly decrease when moving from the back row toward the front row.

Given the number of students and how many students stand in each row, count how many different formations can be used.

Input

The first line contains the number of test cases T.

Each test case consists of two lines. The first line contains the number of rows k. The second line contains k integers n1, n2, ..., nk, separated by spaces, giving the number of students in each row from the back row to the front row.

k is a positive integer not greater than 5, and the total number of students is not greater than 30.

Output

For each test case, print one line containing the number of valid photo formations. The answer is at most 4294967295.

Examples1

  1. Example 1

    Input
    6
1
30
5
1 1 1 1 1
3
3 2 1
4
5 3 3 1
5
6 5 4 3 2
2
15 15
    Expected output
    1
1
16
4158
141892608
9694845