#XMOJ12647. 元胞自动机的逆操作

元胞自动机的逆操作

说明

时间限制:1 Sec 内存限制:256 MB 输入文件:am.in 输出文件:am.out

元胞自动机是一种将地图划分为格子,每个格子的下一状态由相邻格子状态决定的系统。

我们考虑最简单的一维元胞自动机,格子的值只有 $0$ 和 $1$,使用 110 规则。

给定第二行(经过一次 110 变换后的结果),求有多少种可能的第一行,满足:

- 第一行、第二行长度相同,都是环形(左右两端相连)

- 对第一行应用 110 规则恰好得到第二行

110 规则(输入三元组 $(a,b,c)$ 是第一行相邻三个格子,输出 $e$ 是第二行对应位置):

- 如果 $a=1,b=1,c=1$,则 $e=0$

- 如果 $b=0,c=0$,则 $e=0$

- 其余情况,$e=1$

> 等价 110 规则真值表(三元组 $abc → e$)

> 000 → 0

> 001 → 1

> 010 → 1

> 011 → 1

> 100 → 0

> 101 → 1

> 110 → 1

> 111 → 0

输入格式

第一行一个整数 $N$。

接下来 $N$ 行,每行一个整数 $e_i$,代表第二行第 $i$ 位的值。

输出格式

输出合法的第一行方案数,对 $10^9+7$ 取模。

样例

样例 1

4
0
0
0
0

2

样例说明:

合法的第一行只有 0000 和 1111。

样例 2

11
0
1
1
0
1
1
0
1
1
1
0

2

样例 3

6
1
1
1
1
0
1

3

数据范围

对于 35% 的数据,$N \le 5$。

对于 70% 的数据,$N \le 100$。

对于 100% 的数据,$4 \le N \le 2000$,$e_i \in \{0,1\}$。