「KDOI-07」n1gr tS0i

众所周知，小 T 不喜欢 01 串问题，于是小 R 出了另一个有关 01 串的题目：

有一个长度为 $n$ 的 $\tt 01$ 串 $S$，你要对 $S$ 进行 **恰好** $n$ 次操作。每次操作选择 $1 \leq l \color{red}< \color{normal} r \leq n$，然后你按位翻转 $S_{l\dots r}$。这里的按位翻转指，$S_{l\dots r}$ 内所有 $\tt 0$ 同时变为 $\tt 1$，且所有 $\tt 1$ 同时变为 $\tt 0$。 求 $n$ 次操作后，所有可能不同的 $S$ 的个数。因为答案可能很大，所以请对 $998244353$ 取模。

**本题有多组数据。** 第一行一个整数 $T$ 描述数据组数。对于每组数据： - 第一行一个整数 $n$。 - 接下来一行，一个长度为 $n$ 的 $\tt 01$ 串 $S$。

对于每组数据，一行一个整数，表示答案，对 $998244353$ 取模后的结果。

2
2
01
30
101001001010100110101101011110

1
75497471

### 样例解释 - 对于 $n = 2$，$S = \tt 01$，我们会发现每次操作只能选择 $l = 1, r = 2$ 即反转整串，因此 $2$ 次操作后只能得到 $\tt 01$，故答案为 $1$； - 对于第二组数据，暂时不能给你一个明确的答复。 ### 数据规模与约定 **本题采用捆绑测试。** | $\text{Subtask}$ | $n\le$ | 分数 | | :----------: | :----------: | :----------: | | $1$ | $4$ | $30$ | | $2$ | $10^5$ | $70$ | 对于所有数据，保证 $2 \leq n \leq 10^5$，$\sum n \leq 10^6$，$1 \leq T \leq 10^4$。