该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

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

• 若 $b_i=0$，则 $a_i\lt m$；
• 否则 $a_i\gt m$。

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

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

【输入格式】

第一行一个整数 $T$，表示数据组数。 对于每组数据：

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

【输出格式】

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

【样例 1】

3
3
111
3
101
4
0101

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\}$。

【样例 2】

见 century2.in 与 century2.ans

【数据规模与约定】

对于 $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$。