题目描述

杨老师想给他的班级拍一张照片。学生们将排成若干行，要求：

1. 每行的学生数不超过后一行
2. 所有行的左端对齐
3. 每行中学生的身高从左到右递减
4. 从后往前看，每行的学生身高也递减

例如，12个学生可以排列成5、3、3、1的行数：

X X X X X

X X X

X X X

X

对于给定的行数安排，计算满足条件的排列方式总数。

输入格式

• 每组数据两行：
  • 第1行：行数$k$
  • 第2行：从后到前每行的学生数$n_1,n_2,...,n_k$
• 输入以$k=0$结束
• 约束条件：
  • 行数不超过5
  • 学生总数$N$不超过30

输出格式

每组数据输出满足条件的排列方式数

输入样例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

样例解释

• 当所有学生排成1行30列时，只有1种排列方式
• 5行每行1人时，也是1种方式
• 3行3-2-1排列时，有16种方式（如题目中手工计算的例子）
• 其他情况类推

数据范围

• 行数$k$：$1 \leq k \leq 5$
• 每行人数$n_i$：$1 \leq n_i \leq 30$
• 学生总数$N$：$\sum n_i \leq 30$

题目来源

Greater New York 2004