1010. 今晚吃黑子

题目描述

白井黑子喜欢下棋。

她在桌上将 $n$ 枚棋子（黑子或白子）排成一列，从左到右依次编号为 $1$ 到 $n$。

定义一次操作为：选择一个棋子 $i$，满足 $1<i<n$ 且 $i-1$ 和 $i+1$ 处的棋子颜色不同。她会将 $i-1$ 和 $i+1$ 处的棋子吃掉，然后移动棋子将空位填上，形成新的一列棋子，并重新从 $1$ 开始编号。$n$ 也被重新设定为现在棋子序列的长度。

白井黑子可以进行任意（可以为零）次这样的操作。现在，她想让你求出最后可能得到的棋子序列的个数。两个棋子序列不同，当且仅当它们长度不同，或者某个位置棋子的颜色不同。

由于答案可能很大，请输出其对 $998\,244\,353$ 取模后的结果。

输入格式

本题包含多组测试数据。

首先在第一行输入一个整数 $T$（$1\le T\le 10^4$）表示测试数据组数。

接下来对于每一组测试数据：

输入的唯一一行包含一个 01 字符串 $A$（$1\le|A|\le 10^5$），代表初始的棋子颜色，其中黑子是 0。

保证所有测试数据输入的字符串 $A$ 的长度之和不超过 $10^6$。

输出格式

对于每一组测试数据，输出一行一个数，表示可以得到的不同棋子序列的数量对 $998\,244\,353$ 取模的值。

样例输入

2
1101
0100110

样例输出

2
7

提示

对于第一组测试数据，白井黑子可以选择棋子 $2$，并吃掉棋子 $1$ 与 $3$，得到棋子序列 11，加上原序列本身，答案为 $2$。

对于第二组测试数据，白井黑子首先选择棋子 $3$，序列变为 00110；再选择此时的棋子 $2$，序列变为 010。因此这两个序列都应该被统计到答案。

来源：2026杭电多校-测试专用（南外） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1235&pid=1010