题目描述

给定 $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

输入 #1

1
3 3
1 3 7

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

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}$ 对此题的贡献。