你是一名游戏设计师，正在开发一款名为 Outstandingly Captivating Platforming Challenge 的新电子游戏。 该游戏包含 $n$ 个关卡，编号为 $1 \dots n$，玩家必须按此顺序完成。除了正常的关卡进度外，各关卡之间还通过 $n$ 个单向传送门相连。公司里的另一个团队已经完成了每个关卡的设计，他们在每个关卡中都放置了一个传送门入口和一个传送门出口。你的任务是将每个入口连接到一个不同关卡的出口，使得每个出口也只连接到一个入口。

然而，还有一个额外的限制：玩家不能在游戏中跳关。也就是说，玩家不能进入一个传送门，在更靠后的关卡出口处出来，并继续在那个更靠后的关卡中进行游戏。为了实现这一点，关卡设计师将一些出口放置在孤立的位置，从这些位置无法到达关卡的其余部分。具体来说：如果第 $u$ 关的入口连接到第 $v$ 关的出口且 $v > u$，那么第 $v$ 关的出口必须位于孤立位置。

你已经编写了一个程序来检查所有允许的入口到出口的连接方式，以衡量预期的玩家参与度。该程序已经运行了很长时间，你的老板很生气，你想知道这个程序需要运行多久。因此，请计算连接每个入口到出口的允许方式的数量。请输出答案对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 1000$)，表示测试用例的数量。接下来是 $t$ 个测试用例。 每个测试用例包含一个长度为 $n$ ($2 \le n \le 5000$) 的二进制字符串 $s$。如果 $s$ 的第 $i$ 个字符为 $1$，则表示第 $i$ 关的出口位于孤立位置，否则为 $0$。 保证所有测试用例的 $n$ 之和不超过 $5000$。

输出格式

对于每个测试用例，在单独的一行中输出答案对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

4
0101
1010010010001010
11111
10100100011000010010101001001001

样例输出 1

3
0
44
393298077

说明

在第一个样例测试中，有效的配置为 $[2, 1, 4, 3]$、$[2, 4, 1, 3]$ 和 $[4, 1, 2, 3]$，其中数组的第 $i$ 个位置表示连接到第 $i$ 关入口的出口所在的关卡编号。 在第二个样例测试中，没有入口可以连接到最后一关的出口。