Pku2279 Mr. Young's Picture Permutations

杨先生要为班上的学生拍摄合照。所有学生将按若干行站立，各行左端对齐，并且后一行的人数不少于前一行。按照从后向前的顺序，若第 $i$ 行有 $a_i$ 名学生，则满足：

$$a_1 \ge a_2 \ge \cdots \ge a_k$$

所有学生的身高互不相同。每一行中，学生的身高从左到右严格递减；每一列中，学生的身高从后向前严格递减。

对于给定的各行人数，请计算满足上述条件的不同排列方案总数。

输入格式

输入包含多组测试数据。

每组测试数据包含两行：

• 第一行包含一个十进制整数 $k$，表示行数；
• 第二行包含 $k$ 个以单个空格分隔的十进制整数 $a_1,a_2,\ldots,a_k$，按照从后向前的顺序表示各行人数。

当读入的行数为 $0$ 时，输入结束，该行不属于任何一组测试数据。

输出格式

对于每组测试数据，输出一行一个十进制整数，表示满足条件的排列方案总数。

样例输入

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

数据范围

• 行数满足 $k\le 5$；
• 学生总数 $N=\sum_{i=1}^{k}a_i$，且 $N\le 30$；
• 所有学生的身高互不相同；
• 输入保证答案可以用无符号 $32$ 位整数表示。

来源与许可

本题为 POJ 2279「Mr. Young's Picture Permutations」，题面与测试数据整理自 BZOJ 2483。

样例 1

输入

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