小Z的队伍排列

题目描述

小Z想给班里的同学拍一张合影,为此需要先让大家排好队伍。他希望大家站成 k 排,并规定了每排的人数,保证每一排的人数都不多于后面一排的人数。 这时小Z发现队伍看起来还是乱糟糟的,原因是大家的身高互不相同。于是,他希望排头对齐,每位同学都比自己正后方的同学以及排头方向的同学矮。 排完以后,善于思考的小Z还想知道一共有多少种排法。 例如,大家排成 3 排,且从后往前每排分别是 3、2、1 人,就有以下 16 种排法(每个数代表将所有同学身高从高到低排序后该同学的排名): ![](https://cdn.luogu.com.cn/upload/pic/1260.png) 可是班里一共有 n 个人,小Z算不出来了,希望你帮帮他。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

3
3 2 1

输出样例 #1

16

输入样例 #2

5
1 1 1 1 1 

输出样例 #2

1

说明

【数据规模】 对于 30% 的数据,n ≤ 10。 对于另外 30% 的数据,只有最后一排超过 1 个人。 对于 100% 的数据,1 ≤ k ≤ 5,1 ≤ n ≤ 30,方案数小于 2^32。