P9151 Counting Problem

[Easy Counting Problem](https://atcoder.jp/contests/agc022/tasks/agc022_e) > 身のうさを思ひしらでややみなまし そむくならひのなき世なりせば

Given a binary string $S$ of length $N$, you can perform some operations. In each operation, choose a substring of length $3$ and replace it with its median (note that it becomes a single digit). Ask how many different strings can be obtained. Output the answer modulo $998244353$.

This problem has multiple test cases. The first line contains the number of test cases $T$. For each test case, input only one string $S$, representing the given binary string.

For each test case, output one integer per line, which is the answer modulo $998244353$.

**Sample Explanation** It can be proven that $1001$ can only obtain the strings $10$, $01$, and $1001$ through the operations, so the answer for the first test case in the sample is $3$. --- **Constraints** For $100\%$ of the testdata, $1 \le N \le 5\times {10}^6$, $S_i \in \{0,1\}$, and $1 \le T \le 5$. | Subtask | $N \le$ | Special Property | Score | | - | - | - | - | | 1 | $10$ | | $5$ | | 2 | $50$ | | $10$ | | 3 | $300$ | | $10$ | | 4 | $2000$ | | $15$ | | 5 | | A | $5$ | | 6 | | B | $5$ | | 7 | ${10}^5$ | | $20$ | | 8 | | | $30$ | Special Property A: It is guaranteed that $S_i = 0$. Special Property B: It is guaranteed that $S_{2k} = 0$ and $S_{2k+1} = 1$. **String indices start from $1$.** Translated by ChatGPT 5