CF1545B AquaMoon and Chess

你有一个长为 $n$ 的棋盘,这个棋盘上有一些棋子,你可以进行如下操作: 如果第 $i + 2$ 个位置是空的,且第 $i + 1$ 个位置非空,则可以将第 $i$ 个位置的棋子挪到第 $i + 2$ 个位置 ($i + 2 \leq n$). 如果第 $i - 2$ 个位置是空的,且第 $i - 1$ 个位置非空,则可以将第 $i$ 个位置的棋子挪到第 $i - 2$ 个位置 ($i - 2 \geq 1$). 现在将给出一个棋盘的初始状态,求可以通过上述操作可以到达的状态数,你可以进行任意次操作,答案对 $998244353$ 取模.

第一行一个整数 $t(1 \leq t \leq 10000)$ 代表数据组数. 每组数据第一行一个整数 $n(1 \leq n \leq 10^5)$ 代表棋盘大小. 第二行一个长度为 $n$ 的 $01$ 串,第 $i$ 个位置为 $0$ 代表没有棋子,为 $1$ 代表有棋子.

对于每组数据,输出方案数,对 $998244353$ 取模.

In the first test case the strings "1100", "0110" and "0011" are reachable from the initial state with some sequence of operations.