Kevin 正在唐人街探索与二进制字符串相关的问题。正当他不知所措时,一个陌生人走近他,介绍了一个奇特的操作:
- 假设当前的二进制字符串是 $$$ t $$$,长度为 $$$ \vert t \vert $$$。选择一个整数 $$$ 1 \leq p \leq \vert t \vert $$$。对于所有$$$ 1 \leq i < p $$$,同时执行操作$$$ t_i = \max(t_i, t_{i+1}) $$$,然后删除$$$ t_p $$$。
例如,假设当前二进制字符串是 01001,并且您选择 $$$ p = 4 $$$。对$$$t_1$$$、$$$t_2$$$和$$$t_3$$$执行$$$ t_i = \max(t_i, t_{i+1}) $$$,将字符串转换为11001,然后删除$$$ t_4 $$$,结果为1101。
Kevin觉得这个奇怪的操作很有趣。于是,他想问你:给定一个二进制字符串$$$ s $$$,通过任意次数的操作你能得到多少个不同的非空二进制字符串(可能是零)?
由于答案可能非常大,因此只需输出对 $$$998\,244\,353$$$ 取模的结果即可。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t \le 10^4$$$) — 测试用例的数量。
对于每个测试用例,唯一的行包含一个二进制字符串 $$$ s $$$ ($$$ 1 \le \lvert s \rvert \le 10^6 $$$)。
保证所有测试用例的 $$$\lvert s \rvert$$$ 之和不超过 $$$10^6$$$。
输出
对于每个测试用例,在输出的唯一行中打印一个整数 - 您可以获得的不同非空二进制字符串的数量,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
2 11001 000110111001100
输出 #1
9 73
注意
在第一个测试用例中,您可以获得的所有二进制字符串为:11001、1001、1101、001、101、111、01、11和1。总共有$$$ 9 $$$。