题目描述

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

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

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

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

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

输入格式

第一行包含一个整数 k。

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

输出格式

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

输入输出样例

输入 #1复制

33 2 1

输出 #1复制

16

输入 #2复制

51 1 1 1 1

输出 #2复制

1

说明/提示

【数据规模】

对于 30% 的数据，n ≤ 10。

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

对于 100% 的数据，1 ≤ k ≤ 5，1 ≤ n ≤ 30，方案数小于 2^32。

 

emmm 动态规划。。。

 

5排判断