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`$ 没有影响。

我们从前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`$。