Final Group Photo

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.

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.

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