来源：张老师 2026 CSP-J 4＋1 拓展题 20 套；第 10 套，第 3 题。原题标号：C；原本地编号：Z4P1-10-C。

C. Counting Game

对于一个长度为 $n$ 的 01 串 $b$，请求出，有多少个 $n$ 的排列 $a$，满足：对于任意 $2\le i\le n$，记 $m$ 为 $a_1,a_2,\cdots,a_{i-1}$ 中的最大值，

• 若 $b_i=0$，则 $a_i<m$；
• 否则 $a_i>m$。

说明：$b_1$ 对 $a$ 没有影响。

由于结果可能很大，所以你只需要输出结果对 $998244353$​ 取模的值。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

• 第一行一个整数 $n$，意义如题述。
• 第二行一个长度为 $n$ 的 01 串 $b$。

输出格式

对于每组数据，输出一行一个整数，即满足条件的排列的数量，对 $998244353$ 取模。

样例

输入样例 1

3
3
111
3
101
4
0101

输出样例 1

1
1
2

样例 1 说明

• 对于数据 1，唯一的 $a=\{1,2,3\}$。
• 对于数据 2，唯一的 $a=\{2,1,3\}$。
• 对于数据 3，存在两个不同的 $a$：$a=\{1,3,2,4\}$ 或 $a=\{2,3,1,4\}$。

数据规模与约定

对于 $100\%$ 的数据，有 $1\le T\le 10^4$，$2\le n\le 10^6$，$\forall i\in[1,n],b_i\in\{0,1\}$。

保证单个测试点内 $\sum n\le 2\times10^6$。