该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

本题不再额外提供样例文件。

题目描述

$N$ 个方格排成一排。

有 $K$ 种颜色的画笔，第 $i$ 种画笔恰好能涂 $a_i$ 个方格，且所有画笔恰好能涂完所有方格，即 $\sum_{i=1}^K a_i=N$。

现在让你用这些画笔给方格涂色，要求相邻的方格不能涂相同的颜色。

问：你有多少种不同的涂色方案？

两种涂色方案不同，当前仅当至少存在一个格子在两种涂法中所涂的颜色不同。

答案可能很大，你需要将其对 $(10^9+7)$ 取模后输出。

输入格式

第一行，一个整数 $K$

第二行 $K$ 个整数 $a_1,a_2,\dots,a_k$

输出格式

一个整数，表示不同涂色方案数 mod $(10^9+7)$

样例输入 #1

3
1 2 3

样例输出 #1

10

样例输入 #2

10
1 2 3 4 5 2 1 3 1 4

样例输出 #2

701327321

提示

• 对于 $50\%$ 的数据，$1 \leq K \leq 5$，$1 \leq a_i \leq 3$；
• 对于 $100\%$ 的数据，$1 \leq K \leq 15$，$1 \leq a_i \leq 5$。