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$ 代表有棋子。 保证 $\sum n \leq 10^5$。

对于每组数据，输出方案数对 $998244353$ 取模的结果。

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