[EC Final 2022] Binary String

**【题目描述】** 给定一个排列在环上的二进制字符串 $a_0a_1a_2\dots a_{n-1}$。每一秒钟，你会同时将每个 $01$ 变为 $10$。换句话说，如果 $a_i = 0$ 且 $a_{(i+1) \bmod n} = 1$，则交换 $a_i$ 和 $a_{(i+1)\bmod n}$。例如，我们将 $\texttt{100101110}$ 变为 $\texttt{001010111}$。 你需要回答在无限秒内会出现多少种不同的字符串，取模 $998244353$。 注意：如果存在整数 $i\in \{0,1,\ldots, n-1\}$ 使得 $a_i\neq b_i$，则两个字符串 $a_0a_1\dots a_{n-1}$ 和 $b_0b_1\dots b_{n-1}$ 是不同的。因此，字符串的循环移位可能与原始字符串不同。 **【输入格式】** 第一行包含一个整数 $T$ $(1\leq T\leq 10^6)$ $-$ 测试用例的数量。 对于每个测试用例，第一行包含一个二进制字符串 $a_0 a_1 \dots a_{n-1}$ $(a_i \in \{0, 1\})$。 保证所有测试用例中字符串长度的总和不超过 $10^7$。 **【输出格式】** 对于每个测试用例，输出一行一个整数，表示答案。 翻译来自于：[ChatGPT](https://chatgpt.com/)

You are given a binary string $a_0a_1a_2\dots a_{n-1}$ arranged on a cycle. Each second, you will change every $01$ to $10$ simultaneously. In other words, if $a_i = 0$ and $a_{(i+1) \bmod n} = 1$, you swap $a_i$ and $a_{(i+1)\bmod n}$. For example, we will change $\texttt{100101110}$ to $\texttt{001010111}$. You need to answer how many different strings will occur in infinite seconds, modulo $998244353$. Note: Two strings $a_0a_1\dots a_{n-1}$ and $b_0b_1\dots b_{n-1}$ are different if there exists an integer $i\in \{0,1,\ldots, n-1\}$ such that $a_i\neq b_i$. Thus, the cyclic shifts of a string may be different from the original string.

The first line contains an integer $T$ $(1\leq T\leq 10^6)$ $-$ the number of test cases. For each test case, the first line contains a binary string $a_0 a_1 \dots a_{n-1}$ $(a_i \in \{0, 1\})$. It is guaranteed that the sum of lengths of strings over all test cases does not exceed $10^7$.

For each test case, output one integer representing the answer in one line.

3
1
001001
0001111

1
3
9