P17337 【MX-X30-T3】宇宙分解

你有一个 $01$ 序列 $a$ 和两种操作： 1. 选择 $a_i

本题有多组测试。第一行输入一个整数 $T$ 表示测试组数。 每组测试第一行输入一个整数 $n$。 下一行输入一个 $01$ 串，第 $i$ 个字符是 $a_i$。

包含 $T$ 行，第 $i$ 行包含一个整数，表示结束时会得到多少种本质不同的序列。对 $998244353$ 取模。

定义 $s$ 表示每组测试内 $a_i$ 之和的最大值。定义 $N$ 表示所有测试中 $n$ 的和。 | 测试点编号 |$N\le $ | $s\le$ | |:-:|:-:|:-:| | $1\sim 4$ | $200$ | $200$ | | $5\sim 10$ | $10^4$ | $10^3$ | | $11\sim 15$ | $10^5$ | $10^3$| | $16\sim 20$ | $10^5$ |$2\times 10^3$| 对于所有数据，保证 $1\le T\le 10^3$，$1\le n,N\le 10^5$，$0\le s\le 2\times 10^3$。