← 返回题目列表

Codeforces · 1545/B

B. AquaMoon 和国际象棋

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

琪露诺给了水月一个$$$1\times n$$$大小的棋盘。其单元格从左到右用从 $$$1$$$ 到 $$$n$$$ 的整数进行编号。一开始,一些单元格最多被一个棋子占据,而其他单元格未被占据。

在每次操作中,AquaMoon 都可以选择一个带有 pawn 的单元格 $$$i$$$,并执行以下任一操作(如果可能):

- 如果 $$$i+2 \leq n$$$ 且第 $$$(i+1)$$$ 个单元格被占用且第 $$$(i+2)$$$ 个单元格未被占用,则将 pawn 从它移至第 $$$(i+2)$$$ 个单元格。
- 如果 $$$i-2 \geq 1$$$ 并且第 $$$(i-1)$$$ 个单元格被占用并且第 $$$(i-2)$$$ 个单元格未被占用,则将 pawn 从它移到第 $$$(i-2)$$$ 个单元格。

您将获得棋盘的初始状态。 AquaMoon 想要计算通过一些操作序列从初始状态可到达的状态数量。但她不擅长编程。你能帮助她吗?由于答案可能很大,请对 $$$998\,244\,353$$$ 求模。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — 测试用例的数量。

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 棋盘的大小。

第二行包含 $$$n$$$ 个字符的字符串,由字符“0”和“1”组成。如果第$$$i$$$个字符为“1”,则第$$$i$$$个单元格最初被占用;否则,第 $$$i$$$ 个单元格最初未被占用。

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

输出

对于每个测试用例,通过对 $$$998\,244\,353$$$ 进行模运算的某些操作序列,打印从初始状态可到达的状态数。

示例

输入 #1

6
4
0110
6
011011
5
01010
20
10001111110110111000
20
00110110100110111101
20
11101111011000100010

输出 #1

3
6
1
1287
1287
715

注意

在第一个测试用例中,可以通过一些操作序列从初始状态到达字符串“1100”、“0110”和“0011”。