琪露诺给了水月一个$$$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”。