说明

本题不再额外提供样例文件。

题目描述

一个 M 行 N 列的网格图，从上到下依次是第 1 行、第 2 行、……、第 M 行，从左到右依次是第 1 列、第 2 列、……、第 N 列。

现在让你把 1 ~ N 这 N 个数填到方格图中。

要求：

• 从第一行开始，自上而下依次填写每一行。

• 对于每一行，从左到右依次填写每一列。其中第 i 行需要恰好填 $a_i$ 个数。（数据保证 $\sum_{i=1}^M a_i=N$，且 $a_1 ≥ a_2 ≥ …… ≥ a_M$）

• 每一行从左到右要求所填的数要升序排列。每一列从上到下要求所填的数要升序排列。

问：一共有多少种不同的填法？

两种填法不同，当且仅当至少存在一个格子在两种填法中所填写的数不同。

输入

多组数据。每组数据包含两行：

• 第一行：一个整数 M
• 第二行：M 个整数 $a_i$

最后一行以 0 表示结束。

输出

每组数据的答案占一行

输入样例

1
3
3
1 1 1
2
2 1
3
3 2 1
4
4 3 3 2
5
5 4 3 2 1
2
10 10
0

输出样例

1
1
2
16
2970
292864
16796

样例解释

此处仅解释第 3 组数据：

2
2 1

有以下两种填法：

第一种：

1 2
3

第二种：

1 3
2

数据范围

每个测试点不超过 10 组数据。

$1 ≤ M ≤ 5$, 输入数据中没有提到 $N$，可以根据 $a_i$ 的值计算得到 $N = \sum_{i=1}^M a_i$，数据保证 $N ≤ 30$ 且 $a_1 ≥ a_2 ≥ …… ≥ a_M$