#P19009. 【CodeChef START263A】Off by One

【CodeChef START263A】Off by One

题目描述

给定一个长度为 N−1N-1 的 01 串 SS。请统计有多少个由 11 到 NN 各出现一次组成的排列 PP 满足以下条件。

  • 若 Si=1S_i=1,则 PiP_i 与 Pi+1P_{i+1} 的差的绝对值等于 11。
  • 若 Si=0S_i=0,则 PiP_i 与 Pi+1P_{i+1} 的差的绝对值不等于 11。

上述要求对每个 1≤i<N1\le i<N 都成立。答案对 998244353998244353 取模。

输入格式

第一行一个整数 TT,表示测试组数。每组两行,第一行一个整数 NN,第二行一个由字符 0 和 1 组成的字符串 SS,长度为 N−1N-1。

输出格式

每组输出一行一个整数,表示满足条件的排列数对 998244353998244353 取模的结果。

数据范围

  • 1≤T≤1051\le T\le 10^5。
  • 2≤N≤40002\le N\le 4000。
  • 单个输入文件内所有测试组的 N2N^2 之和不超过 400024000^2。

样例

4
4
000
5
0101
6
01001
16
010001001000010
2
14
42
228019520

来源 CodeChef START263A · OFFBYONE。