题目描述

有 $N$ 个学生合影，站成左端对齐的 $k$ 排，每排分别有 $N_1, N_2, \dots, N_k$ 个人，满足 $N_1 \ge N_2 \ge \dots \ge N_k$。

第 $1$ 排站在最后边（最高），第 $k$ 排站在最前边（最矮）。

学生的身高互不相同，把他们从高到低依次标记为 $1, 2, \dots, N$（$1$ 最高，$N$ 最矮）。

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

问一共有多少种安排合影位置的方案？

输入格式

输入包含多组测试数据。

每组数据两行，第一行包含一个整数 $k$ 表示总排数。

第二行包含 $k$ 个整数，表示从后向前（即第 $1$ 排到第 $k$ 排）每排的具体人数。

当输入 $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=1$，只有一排 $30$ 人，从左到右递减，只有 $1$ 种排列（$1,2,\dots,30$ 从左到右），输出 $1$。
• $k=5$，每排 $1$ 人，共 $5$ 人，满足每排每列递减，其实相当于 $5$ 人站成一列，只有 $1$ 种排列（从上到下 $1,2,3,4,5$），输出 $1$。
• $k=3$，每排 $3,2,1$ 人（共 $6$ 人），即题目开头描述的情况，有 $16$ 种方案，输出 $16$。
• 其他情况类似计算。

数据范围

• $1 \le k \le 5$
• 学生总人数不超过 $30$ 人

时空限制

• 时间限制：1 秒
• 空间限制：64 MB