在玩蜡笔感到无聊后,您决定改用乐高积木!今天,您正在处理一条长条,高度为 $$$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$$$ 操作,因为不可能达到最终状态。