Migrated from Lutece 2059 世上最幸福的女孩

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在Sakura生命的最后时光，子辉希望给 Sakura 留下美好的回忆，他决定送 Sakura一个漂亮的围巾。

围巾被划分成$n$个块，排成一行，从左到右依次编号为1~n。子辉有$k$种颜色的染色剂，其中第$i$种颜色的染色剂足够染$c_i$块。 所有油漆刚好足够涂满所有块，即 $c_1+c_2+...+c_k=n$。相邻两个块涂相同颜色会显得很难看，所以子辉希望统计任意两个相邻块颜色不同的着色方案。

子辉捧着那个漂亮的围巾来到Sakura的病床前，亲手给病床上的Sakura戴上，虽然此时的Sakura因为疾病的原因显得十分憔悴，但戴上围巾的Sakura依然美若仙子。

“所以，我敢肯定，现在的我，不管别人怎么说，都一定是世界上最幸福的女孩。” Sakura满脸幸福。

Input

第一行为一个正整数k，第二行包含k个整数$c_1$, $c_2$, ... , $c_k$。

100%的数据满足：$1 \le k \le 15, 1 \le c_i \le 5$

Output

输出一个整数，即方案总数模$10^9+7$的结果。

Samples

3
1 2 3

10

Resources

2018 UESTC Training for Dynamic Programming