AquaMoon and Chess

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

有一个长度为 $n$ 的棋盘。每个位置或者为空，或者放有一枚棋子。你可以进行任意次下列操作：

• 如果位置 $i$ 和 $i+1$ 上都有棋子，且位置 $i+2$ 为空，则把位置 $i$ 上的棋子移动到位置 $i+2$；
• 如果位置 $i$ 和 $i-1$ 上都有棋子，且位置 $i-2$ 为空，则把位置 $i$ 上的棋子移动到位置 $i-2$。

给定棋盘的初始状态，求能够到达的不同棋盘状态数。答案对 $998244353$ 取模。

输入格式

第一行包含一个整数 $t$，表示测试数据组数。

每组数据包含两行：第一行一个整数 $n$；第二行一个长度为 $n$ 的 01 串。字符 0 表示空位，字符 1 表示有棋子。

输出格式

对每组数据输出一行一个整数，表示可达状态数对 $998244353$ 取模的结果。

样例输入 1

6
4
0110
6
011011
5
01010
20
10001111110110111000
20
00110110100110111101
20
11101111011000100010

样例输出 1

3
6
1
1287
1287
715

数据范围

对于全部数据，$1\le t\le 10^4$，$1\le n\le 10^5$，且单个输入文件中所有测试数据的 $n$ 之和不超过 $10^5$。