No submission language available for this problem.

题目描述

运动会到了，小 A 作为体育委员，要安排班级进行阵列练习，以备运动会入场式。

阵列的安排是需要将班级的学生站成左边对齐的 k 排，每排人数是非严格递减。($N_1≥N_2≥…≥N_k$)

学生的身高互不相同，把他们从高到底依次标记为 1, 2, …, N。

在合影时要求每一排从左到右身高递减，每一列从后到前身高也递减。

问若准备安排去排阵列的学生共 N 人，排 k 排，每排 $n_1, n_2 ... n_k$, 那么一共有多少种安排合影位置的方案？

举个例子 $N=6,k=3,N1=3,N2=2,N3=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≤k≤5$, 学生总人数不超过 $30$ 人。

样例 #1

样例输入 #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
1
16
4158
141892608
9694845