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 自动生成