← 返回题目列表

Codeforces · 1615/F

F. 传奇大师

中文机器翻译题面 查看原题

在玩蜡笔感到无聊后,您决定改用乐高积木!今天,您正在处理一条长条,高度为 $$$1$$$,长度为 $$$n$$$,其中一些位置被 $$$1$$$ 和 $$$1$$$ 乐高积木占据。

在一秒钟内,您可以从条带上移除两个相邻的乐高积木(如果两者都存在),或者将两个乐高积木添加到相邻位置(如果两者都不存在)。您只能同时在两个相邻位置添加或删除乐高积木,否则您的胖手指会遇到精度问题。

您想确切地知道您会花多少时间玩乐高积木。您重视效率,因此给定一些开始状态和一些结束状态,您总是会花费最少的秒数将开始状态转换为结束状态。如果无法将起始状态转换为结束状态,您只需跳过它(因此您会花费 $$$0$$$ 秒)。

问题是,对于某些位置,您不记得那里是否有乐高积木(在开始状态、结束状态或两者都有)。在与您的记忆一致的所有对(开始状态、结束状态)中,找出将开始状态转换为结束状态所需的总时间。打印该值对 $$$1\,000\,000\,007$$$ 取模 ($$$10^9 + 7$$$)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。然后是 $$$t$$$ 案例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2000$$$) — 乐高带的大小。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符 0、1 和 ? 组成。 — 你对起始状态的记忆:

- 1代表肯定有乐高积木的位置,
- 0代表绝对没有乐高积木的位置,
- 和?代表一个你不记得的位置。

每个测试用例的第三行包含一个长度为 $$$n$$$ 的字符串 $$$t$$$,由字符 0、1 和 ? 组成。 ——你对结束状态的记忆。它遵循与起始状态类似的格式。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,输出一个整数 - 问题的答案以 $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$) 为模。

示例

输入 #1

6
2
00
11
3
???
???
3
??1
0?0
4
??0?
??11
5
?????
0??1?
10
?01??01?1?
??100?1???

输出 #1

1
16
1
14
101
1674

注意

对于第一个测试用例,$$$00$$$ 是唯一可能的起始状态,$$$11$$$ 是唯一可能的结束状态。只需一次操作即可将 $$$00$$$ 更改为 $$$11$$$。

对于第二个测试用例,一些可能的开始和结束状态对是:

- $$$(000, 011)$$$ — 需要 $$$1$$$ 操作。
- $$$(001, 100)$$$ — 需要 $$$2$$$ 操作。
- $$$(010, 000)$$$ — 需要 $$$0$$$ 操作,因为不可能达到最终状态。