P10877 "KDOI-07" n1gr tS0i

As everyone knows, Little T does not like 01 string problems, so Little R made another problem about 01 strings.

There is a $\tt 01$ string $S$ of length $n$. You need to perform **exactly** $n$ operations on $S$. In each operation, choose $1 \le l \color{red}< \color{normal} r \le n$, and then flip $S_{l\dots r}$ bit by bit. Here, “flip bit by bit” means that all $\tt 0$ in $S_{l\dots r}$ become $\tt 1$ at the same time, and all $\tt 1$ become $\tt 0$ at the same time. After $n$ operations, find the number of all possible distinct strings $S$. Since the answer may be very large, output it modulo $998244353$.

**This problem has multiple test cases.** The first line contains an integer $T$ describing the number of test cases. For each test case: - The first line contains an integer $n$. - The next line contains a $\tt 01$ string $S$ of length $n$.

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

### Sample Explanation - For $n = 2$, $S = \tt 01$, we will find that in each operation we can only choose $l = 1, r = 2$, that is, flipping the whole string. Therefore, after $2$ operations we can only get $\tt 01$, so the answer is $1$. - For the second test case, we cannot give you a clear answer for now. ### Constraints **This problem uses bundled testdata.** | $\text{Subtask}$ | $n\le$ | Score | | :----------: | :----------: | :----------: | | $1$ | $4$ | $30$ | | $2$ | $10^5$ | $70$ | For all testdata, it is guaranteed that $2 \le n \le 10^5$, $\sum n \le 10^6$, and $1 \le T \le 10^4$. Translated by ChatGPT 5