#2893. 扩展九连环

扩展九连环

题目背景

提示:此题有大样例。

提示:本题中的九连环不允许 1,21,2 环同时上或下,与传统九连环不同。

九连环是一种源于中国的传统智力游戏。如图所示,九个的圆环套在一把“剑”上,并且互相牵连。

在传统的九连环中,第 k(k2)k(k\ge 2) 个环可以装上“剑”(记为 11)或拆下“剑”(记为 00),当且仅当第 k1k-1 个环在剑上,且再之前的环不在剑上;特别地,第 11 个环可以任意上下。

本题中我们将会讨论更一般的情形,虽然这种扩展九连环不一定可以在物理意义上造出。

题目描述

一个扩展九连环,可以看作两个 01 串——规则串 ss 和状态串 tt,满足 s=t1|s|=|t|-1。其中 ti=1t_i = \texttt 1 表示第 ii 个环是装上的,ti=0t_i = \texttt 0 表示第 ii 个环是拆下的。

ss 在同一局游戏中是不变的,而 tt 每步会变化一个位置上的值(从 0 变成 1 或从 1 变成 0)。九连环被拆下,当且仅当 tit_i 全是 0;九连环被装上,当且仅当 tit_i 全是 1

扩展九连环规定,tit_i 可以变化,当且仅当 t1i1t_{1\sim i-1}ss 的一个后缀。可以看出,传统的九连环就是 ss00...01 的特殊情形。

给出一个 ss,问从拆下状态到装上状态至少需要几步,答案对 109+710^9+7 取模。

输入格式

第一行一个整数 nn,表示 ss 的长度。注意不是环的数量。

第二行一个 01ss

输出格式

一行一个整数,表示答案对 109+710^9+7 取模后的值。

样例

3
011
6
8
00000001
341

样例 #3 见附件

样例 #4 见附件

提示

样例 1 解释

初始时刻所有环都不在剑上,状态串 tt0000

第 1 步装上第 11 个环,tt 变成 1000

第 2 步装上第 22 个环,tt 变成 1100

第 3 步装上第 33 个环,tt 变成 1110

接下来你不能直接装上第 44 个环,因为 111 并不是规则串 ss 011 的后缀。因此第 4 步应拆下第 11 个环,tt 变成 0110

然后第 5 步装上第 44 个环,tt 变成 0111

最后一步装上第 11 个环,tt 变成 1111,完成目标。

样例 2 解释

这就是传统的九连环,且恰好有 99 个环。

样例 3 解释

样例 3 满足测试点 77 的限制。

样例 4 解释

样例 4 满足测试点 1515 的限制。

数据范围

对于 100%100\% 的数据,1n20001\le n\le 2000si{0,1}s_i\in\{\texttt 0,\texttt 1\}

测试点编号 s\vert s\vert\le 特殊性质
131\sim 3 33
464\sim 6 1515
7117\sim 11 300300
121312\sim 13 10001000
1414 20002000 sis_i 全为 0
151715\sim 17 ss 末尾为 1,其余位置为 0
182518\sim 25