You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

有N个学生排排坐，站成左端对齐的k排，每排都有$N_1$,$N_2$，$N_3$···$N_k$第1排站在最后边，第k排站在最前边

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

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

Description

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

下面的一排三角矩阵给出了当$N=6,k=3,N_1=3,N_2=2,N_3=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

Format

Input

输入包含多组测试数据。

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

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

当输入k=0的数据时，表示输入终止，且该数据无需处理。

Output

一共有多少种安排座位位置的方案

Samples

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

Limitation

1s, 1024KiB for each test case.