AT_joi2019_yo_f 座席 (Seats)

2XXX 年，全球的国家都排成了一条直线，共有 $N$ 个国家，编号依次为 $1, 2, \ldots, N$。每个相邻序号的国家都是邻国。 在今年的国际信息学奥林匹克竞赛中，编号为 $i$ 的国家将派出 $A_i$ 名选手参赛。作为竞赛的技术委员会成员，你需要为比赛安排座位。由于场地狭窄，所有选手只能坐在一排总共 $A_1 + A_2 + \cdots + A_N$ 个座位上。为了防止作弊，规定同一国家或邻国的选手不能相邻而坐。 请问有多少种不同的方法可以安排座位？由于这个数字可能非常大，只需输出将其对 $10007$ 取模后的结果。

输入包含一个整数序列，表示： > $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出一个整数，表示合法座位安排的方法数对 $10007$ 取模的结果。

### 约束条件 - $1 \leq N \leq 100$ - $1 \leq A_i \leq 4$ ($1 \leq i \leq N$) ### 子问题 1. （6 分）$N \leq 5$ 且 $A_i \leq 2$ 2. （14 分）$N \leq 10$ 且 $A_i \leq 3$ 3. （80 分）无其它限制 ### 示例解释 1 假设国家 $1$ 的两名选手记为 $1$ 和 $1'$，国家 $2$ 的一名选手记为 $2$，国家 $3$ 的一名选手记为 $3$，国家 $4$ 的一名选手记为 $4$，那么符合条件的座位安排有以下四种： - $1$, $3$, $1'$, $4$, $2$ - $1'$, $3$, $1$, $4$, $2$ - $2$, $4$, $1$, $3$, $1'$ - $2$, $4$, $1'$, $3$, $1$ ### 示例解释 2 在这个输入例子中，没有任何一种座位安排可以满足条件。 ### 示例解释 3 在这一例子中，有 $24768$ 种不同的安排方式，因此输出它对 $10007$ 取模后的结果 $4754$。 **本翻译由 AI 自动生成**