题目描述

小 Y 正在玩一个连线游戏，名叫“此路不通”。

游戏中有 $n$ 个入口和 $n$ 个出口，编号都是 $1,2,\dots,n$。

现在小 Y 需要将每个入口连向一个出口，并且出口必须被恰好一个入口连接，并且连接的入口编号和出口编号不能相同。

然而出口的点有一些是安全的，剩下的都是陷阱。只有安全的出口才可以离开。

我们称一个连法是符合“此路不通”的，当且仅当不管从任何入口 $i$ 出发，都不会从编号大于 $i$ 的出口离开。

现在给定哪些出口是陷阱，请你判断有多少种连法，是“此路不通”的。两个连法不同当且仅当某个入口连接的出口在两个方案中不同。答案对 $998244353$ 取模。

输入格式

从 stop.in 文件读入数据。

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

对于每个测试数据，输入一行一个 $01$ 串，长度为 $n$，第 $i$ 个字符为 0 代表编号 $i$ 的出口是安全的，否则字符为 1 代表编号 $i$ 的出口是有陷阱的。

输出格式

输出到 stop.out 文件。

对于每个测试数据，输出一行一个整数，代表答案，对 $998244353$ 取模。

样例 1

4
0101
1010010010001010
11111
10100100011000010010101001001001

3
0
44
393298077

第一个样例可能的连接方法：

1. 入口 1 - 出口 2， 入口 2 - 出口 1， 入口 3 - 出口4， 入口 4 - 出口 3
2. 入口 1 - 出口 4， 入口 2 - 出口 1， 入口 3 - 出口2， 入口 4 - 出口 3
3. 入口 1 - 出口 2， 入口 2 - 出口 4， 入口 3 - 出口1， 入口 4 - 出口 3

样例 2

点击链接 ex_stop2.in 和 ex_stop2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于每个测试点， 保证 $1\le t\le 1000, 1\le \sum n\le 5000$