CF1545B.AquaMoon and Chess

Cirno gave AquaMoon a chessboard of size $1 \times n$. Its cells are numbered with integers from $1$ to $n$ from left to right. In the beginning, some of the cells are occupied with at most one pawn, and other cells are unoccupied.

In each operation, AquaMoon can choose a cell $i$ with a pawn, and do either of the following (if possible):

• Move pawn from it to the $(i+2)$-th cell, if $i+2 \leq n$ and the $(i+1)$-th cell is occupied and the $(i+2)$-th cell is unoccupied.
• Move pawn from it to the $(i-2)$-th cell, if $i-2 \geq 1$ and the $(i-1)$-th cell is occupied and the $(i-2)$-th cell is unoccupied.

You are given an initial state of the chessboard. AquaMoon wants to count the number of states reachable from the initial state with some sequence of operations. But she is not good at programming. Can you help her? As the answer can be large find it modulo $998\,244\,353$.

Cirno 给了 AquaMoon 一个大小为 $1 \times n$ 的棋盘。其单元格从左到右依次编号为 $1$ 到 $n$。初始时，某些单元格中至多放置一枚兵（pawn），其余单元格为空。

在每次操作中，AquaMoon 可以选择一个有兵的单元格 $i$，并执行以下两种操作之一（若可行）：

• 若 $i+2 \leq n$，且第 $(i+1)$ 个单元格被占据、第 $(i+2)$ 个单元格为空，则可将该兵移动至第 $(i+2)$ 个单元格；
• 若 $i-2 \geq 1$，且第 $(i-1)$ 个单元格被占据、第 $(i-2)$ 个单元格为空，则可将该兵移动至第 $(i-2)$ 个单元格。

你将获得棋盘的初始状态。AquaMoon 想要计算：从该初始状态出发，经若干次操作后所能到达的不同状态的总数。但她不擅长编程。你能帮她吗？由于答案可能很大，请对 $998\,244\,353$ 取模输出结果。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10\,000$) — the number of test cases.

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the size of the chessboard.

The second line contains a string of $n$ characters, consists of characters "0" and "1". If the $i$-th character is "1", the $i$-th cell is initially occupied; otherwise, the $i$-th cell is initially unoccupied.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10\,000$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示棋盘的大小。

第二行包含一个长度为 $n$ 的字符串，仅由字符 "0" 和 "1" 组成。若第 $i$ 个字符为 "1"，则第 $i$ 个格子初始时被占据；否则，第 $i$ 个格子初始时为空。

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

For each test case, print the number of states that reachable from the initial state with some sequence of operations modulo $998\,244\,353$.

对于每个测试用例，输出从初始状态出发、通过若干次操作可达的状态数量，结果对 $998\,244\,353$ 取模。

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

在第一个测试用例中，字符串 “1100”、“0110” 和 “0011” 均可通过若干次操作从初始状态到达。