题目描述

我们定义一个仅包含 0 和 1 的序列 \(S\) 是茄子序列，当且仅当该序列中逆序对的数量是奇数（逆序对数量等同于序列中 “10” 子序列的数量，比如序列 “10100”中逆序对数量为 \(5\)）。

我们定义 \(f(S)\) 为最小的正整数 \(k\)，使得我们可以将 01 序列 \(S\) 划分成 \(k\) 个子段，每个子段都是茄子序列。

特殊的，如果一个序列 \(S\) 无论如何划分都不能满足条件，我们定义 \(f(S) = 0\)。

给定一个仅包含 0 和 1 的序列 \(S\)，求出 \(S\) 的所有非空子序列的 \(f\) 值之和（ 序列 \(S\) 有 \(2^{|S|}-1\) 个非空子序列）。

我们定义一个序列的子序列为删除原序列任意位置任意个元素后，将剩余元素首尾相接得到的元素。

由于答案较大，你只需要输出答案在模 \(998244353\) 意义下的结果即可。

输入格式

第一行输入一个整数 \(T\) 表示测试数据组数。

接下来 \(T\) 行每行输入一个字符串 \(S\)。

\(1 \le T \le 5\)。

保证所有输入的字符串 \(S\) 的总长度不超过 \(10^7\)。

输出格式

输出 \(T\) 行，每行一个整数，表示答案在模 \(998244353\) 意义下的结果。

样例输入

3
1100
10110010
01101001100101101001011001101001

样例输出

4
160
981596155