问题描述

在2XXX年，世界上的国家们直线排列。共有N个国家，它们被编号为1, 2, ..., N。对于每个i = 1, 2, ..., N - 1，国家i和国家i + 1是相邻国家。

在这一年的国际信息学奥林匹克竞赛中，来自国家i的选手人数为$A_i$。作为国际信息学奥林匹克技术委员会的成员，您负责制定比赛的座位表。由于比赛场地很长而狭窄，选手们需要分配到排成一列的$A_1 + A_2 + ... + A_N$个座位上。为了防止作弊，不能将同一国家或相邻国家的选手分配到相邻的座位上。

有多少种方式可以将选手分配到座位上？由于数量可能非常大，所以希望求出除以10007的余数。

约束条件

• $1 \leq N \leq 100$
• $1 \leq A_i \leq 4$ ($1 \leq i \leq N$)

输入

从标准输入中以以下格式给出输入：

$N$ $A_1$ $A_2$ $...$ $A_N$

输出

要求将选手分配到座位上的方式数量以1行输出，输出结果取模$10007$。

子问题

1. ($6$ 分) $N \leq 5$，$A_i \leq 2$ ($1 \leq i \leq N$)
2. ($14$ 分) $N \leq 10$，$A_i \leq 3$ ($1 \leq i \leq N$)
3. ($80$ 分) 没有额外的约束条件。

输入示例 1

4
2 1 1 1

输出示例 1

4

假设从国家1有2名选手，分别记为1和1'，从国家2有1名选手，记为2，从国家3有1名选手，记为3，从国家4有1名选手，记为4。那么，可以考虑以下4种座位安排方式：

• 1, 3, 1', 4, 2
• 1', 3, 1, 4, 2
• 2, 4, 1, 3, 1'
• 2, 4, 1', 3, 1

输入示例 2

5
1 2 3 2 1

输出示例 2

0

在这个输入示例中，不存在满足条件的座位表。

输入示例 3

6
1 2 3 3 2 1

输出示例 3

4754

在这个输入示例中，有24768种将选手分配到座位上的方式，因此将这个数除以10007后得到余数4754，输出4754。