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

数数游戏

对于一个长度为 $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$ 没有影响。

我们从前i项推广到第i+1项

前4项的相对大小1,4,3,2

在第五项插入一个数，如果它是前五项的最大值1,4,3,2,5

第二大值:1,5,3,2,4

第三大：1,5,4,2,3

第四大:1,5,4,3,2

第五大:2,5,4,3,1

任意一个长度为 $n$ 的排列，通过确定第 $n+1$ 项在前 $n+1$ 项是第几大，可以得到一个唯一的长度为 $n+1$ 的排列。

$f_i$ 为满足前 $i$ 项相对大小的排列个数。

$b_i=1$，必须是前若干项的最大值，$f_{i}=f_{i-1}$

$b_i=0$，可以是第二大，第三大，第四大，…,第i大，i-1种情况，$f_i=(i-1) \times f_(i-1)$ 由于结果可能很大，所以你只需要输出结果对 $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$。