说明

有一个长度为 $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$；
• 对于第二组数据，暂时不能给你一个明确的答复。

数据规模与约定

本题采用捆绑测试。

对于所有数据，保证 $2 \leq n \leq 10^5$，$\sum n \leq 10^6$，$1 \leq T \leq 10^4$。