GNYR04H - Mr Youngs Picture Permutations

### 题目大意： 有 $N$ 个学生合影，站成左端对齐的 $k$ 排，每排分别有 $N_1,N_2,\cdots,N_k$ 个人$（N_1\geq N_2\geq\cdots\geq N_k）$。 第 $1$ 排站在最后边，第 $k$ 排站在最前边。 学生的身高互不相同，把他们从高到底依次标记为 $1,2,\cdots,N$。 在合影时要求每一排从左到右身高递减，每一列从后到前身高也递减。 问一共有多少种安排合影位置的方案？ 下面的一排三角矩阵给出了当 $N=6$，$k=3$，$N_1=3$，$N_2=2$，$N_3=1$ 时的全部 $16$ 种合影方案。注意身高最高的是 $1$，最低的是 $6$。 ``` 123 123 124 124 125 125 126 126 134 134 135 135 136 136 145 146 45 46 35 36 34 36 34 35 25 26 24 26 24 25 26 25 6 5 6 5 6 4 5 4 6 5 6 4 5 4 3 3 ``` ### 输入格式： 输入包含多组测试数据。 每组数据两行，第一行包含一个整数 $k$ 表示总排数。 第二行包含 $k$ 个整数，表示从后向前每排的具体人数。 当输入 $k=0$ 的数据时，表示输入终止，且该数据无需处理。 ### 输出格式 每组测试数据输出一个答案，表示不同安排的数量。 每个答案占一行。 ### 数据范围 $1\leq k\leq 5$,学生总人数不超过 $30$ 人。 ### 输入样例 ``` 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 0 ``` ### 输出样例 ``` 1 1 16 4158 141892608 9694845 ```

Mr. Young wishes to take a picture of his class. The students will stand in rows, with each row no longer than the row behind it and the left ends of the rows aligned. For instance, 12 students could be arranged in rows (from back to front) of 5, 3, 3 and 1 students. ``` X X X X X X X X X X X X ``` In addition, Mr. Young wants the students in each row arranged so that heights decrease from left to right. Also, student heights should decrease from the back to the front. Thinking about it, Mr. Young sees that for the 12-student example, there are at least two ways to arrange the students (numbers represent heights, with 1 meaning the tallest): ``` 1 2 3 4 5 1 5 8 11 12 6 7 8 2 6 9 9 10 11 3 7 10 12 4 ``` Mr. Young wonders how many different arrangements of the students there might be for a given arrangement of rows. He tries counting by hand starting with rows of lengths 3, 2 and 1 and counts 16 arrangements: ``` 123 123 124 124 125 125 126 126 134 134 135 135 136 136 145 146 45 46 35 36 34 36 34 35 25 26 24 26 24 25 26 25 6 5 6 5 6 4 5 4 6 5 6 4 5 4 3 3 ``` Mr. Young sees that counting by hand is not going to be very effective for any reasonable number of students. He asks you to help out by writing a computer program to determine the number of different arrangements of students for a given set of rows. Input ===== The input describes a series of test, each described in two lines. The first line gives the number of rows, _k_, as a decimal integer. The second line contains the lengths of the rows from back to front (_n_ $ _{1} $ ,_n_ $ _{2} $ ,..., _n_ $ _{k} $ ) as decimal integers separated by single spaces. The problem set ends with a line with a row count of 0. There will never be more than 5 rows and the total number of students, _N_, (sum of the row lengths) will be at most 30. Output ====== For each test case output a single integer: The number of arrangements of _N_ students into the given rows, so that the heights decrease along each row from left to right and along each column from back to front (assume that all heights are distinct). The results should be in separate lines. The input data will be chosen so that the result will always fit in an unsigned 32-bit integer. Sample ====== Input ``` 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 0 ``` Output ``` 1 1 16 4158 141892608 9694845 ```