『MdOI R4』Phoenix

这是 $6$ 题中唯一一道没有题目背景的题。

给定 $n$ 个**不可重**集合 $s_1\dots s_n$，集合中的数都是 $[1,m]$ 的范围内的整数。 现在请你求出有多少种 $1\sim n$ 的排列 $p$，使得 $(\sum\limits_{i=1}^n |s_i|)-(\sum\limits_{i=1}^{n-1} |s_{p_i}\bigcap s_{p_{i+1}}|)=|\bigcup\limits_{i=1}^n s_i|$ 成立。 答案对 $998244353$ 取模。保证取模前的真实答案大于 $0$。

**本题有多组数据。** 第一行一个正整数 $T$ 表示数据组数，对于每组数据： 第一行两个正整数 $n,m$。 第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，每个正整数代表一个状态压缩下的集合，若 $a_i$ 在二进制下从低位往高位的第 $k$ 位是 $1$，则 $s_i$ 包含 $k$，否则 $s_i$ 不包含 $k$。

$T$ 行，每行对应一组测试数据。 对于每组数据，一行一个整数表示答案。

1
3 3
1 3 7

4

2
5 9
2 30 98 386 482
4 2 
1 3 3 1

12
12

【样例解释 #1】 三个集合分别为 $\{1\},\{1,2\},\{1,2,3\}$。 共有四个排列符合条件，分别是 $(1,2,3),(1,3,2),(2,3,1),(3,2,1)$。 【数据规模与约定】 **本题采用捆绑测试** |子任务编号|$n\le$|$m\le$|特殊性质|分值| |:-|:-|:-|:-|:-| |$1$|$10$|$20$|无特殊限制|$10$| |$2$|$30$|无特殊限制|$a_i=2^i$|$10$| |$3$|无特殊限制|无特殊限制|$a_i\operatorname{or}a_j=\max(a_i,a_j)$|$10$| |$4$|无特殊限制|无特殊限制|每个集合恰好包含两个元素|$20$| |$5$|无特殊限制|$20$|无特殊限制|$20$| |$6$|无特殊限制|无特殊限制|无特殊限制|$30$| 对于 $100\%$ 的数据，$1 \le T \le 50$，$1\le \sum n\le 10^5$，$1\le m\le 60$，$0 \le a_i \le 2^m-1$，其中 $\sum n$ 表示所有测试数据中 $n$ 的和。 【提示与帮助】 本题读入量较大，请选手选择较快的读入方式。 感谢 $\rm\textcolor{black}{J}\textcolor{red}{ohnVictor}$ 对此题的贡献。