题目描述

小 Z 想给班里的同学拍一张合影，为此需要先让大家排好队伍。他希望大家站成 $k$ 排，并规定了每排的人数，保证每一排的人数都不多于后面一排的人数。

这时小 Z 发现队伍看起来还是乱糟糟的，原因是大家的身高互不相同。于是，他希望排头对齐，每位同学都比自己正后方的同学以及排头方向的同学矮。

排完以后，善于思考的小 Z 还想知道一共有多少种排法。

例如，大家排成 $3$ 排，且从后往前每排分别是 $3$ 、 $2$ 、 $1$ 人，就有以下 $16$ 种排法（每个数代表将所有同学身高从高到低排序后该同学的排名）：

$$\begin{matrix} 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 \end{matrix}$$

可是班里一共有 $n$ 个人，小 Z 算不出来了，希望你帮帮他。

输入格式

第一行包含一个整数 $k$。

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

输出格式

一行，包含一个整数，表示队伍排列的方案数。

3
3 2 1

16

5
1 1 1 1 1 

1

提示

数据范围及约定

对于 $30\%$ 的数据，$n \le 10$。

对于另外 $30\%$ 的数据，只有最后一排超过 $1$ 个人。

对于 $100\%$ 的数据，$1 \le k \le 5$，$1 \le n \le 30$，方案数小于 $2^{32}$。