AT_nyc2015_5 ひも

有 $N$ 个人正在睡觉。すぬけ君打算用 $N-1$ 根绳子将这些人连接起来。 - 每根绳子可以将两个人的两端连接起来，从而使这两个人被连接。 - 要保证任意两个人都可以通过直接或间接的方式被绳子连接在一起。 - 第 $i$ 个人恰好要连接 $a_i$ 根绳子。 请问有多少种不同的连接绳子的方式？请将答案对 $1,000,000,007$ 取模后输出。 绳子没有区分。

输入的第一行为一个整数 $N$，表示人数。 接下来的 $N$ 行，每行一个整数 $a_i$，表示第 $i$ 个人需要连接的绳子数。

输出一个整数，表示满足条件的连接方式数，对 $1,000,000,007$ 取模。

### 数据范围 - $2 \leq N \leq 100000$ - $1 \leq a_i \leq 3$ 由 ChatGPT 4.1 翻译