Background

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

Problem Description

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$.

Input Format

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$.

Output Format

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

2
2
01
30
101001001010100110101101011110

1
75497471

Hint

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.

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