Description

Given $n$ distinct sets $s_1 \dots s_n$, where all numbers in the sets are integers within the range $[1, m]$.

Now you need to find how many permutations $p$ of $1 \sim n$ satisfy

$$(\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|$$

The answer should be taken modulo $998244353$. It is guaranteed that the real answer before taking modulo is greater than $0$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$ indicating the number of test cases. For each test case:

The first line contains two positive integers $n, m$.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$. Each positive integer represents a set under state compression. If the $k$-th bit (from low to high) of $a_i$ in binary is $1$, then $s_i$ contains $k$; otherwise, $s_i$ does not contain $k$.

Output Format

Output $T$ lines, each corresponding to one test case.

For each test case, output one integer per line indicating the answer.

1
3 3
1 3 7

4

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

12
12

Hint

[Sample Explanation #1]

The three sets are $\{1\}, \{1,2\}, \{1,2,3\}$.

There are $4$ permutations that satisfy the condition: $(1,2,3), (1,3,2), (2,3,1), (3,2,1)$.

[Constraints and Agreements]

This problem uses bundled testdata.

Subtask ID	$n \le$	$m \le$	Special Property	Score
$1$	$10$	$20$	No special restrictions	$10$
$2$	$30$	No special restrictions	$a_i = 2^i$
$3$	No special restrictions		$a_i \operatorname{or} a_j = \max(a_i, a_j)$
$4$			Each set contains exactly two elements	$20$
$5$		$20$	No special restrictions
$6$		No special restrictions		$30$

For $100\%$ of the testdata, $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$, where $\sum n$ denotes the sum of $n$ over all test cases.

[Tips and Help]

The input size of this problem is large, so please choose a faster input method.

Thanks to $\rm\textcolor{black}{J}\textcolor{red}{ohnVictor}$ for contributing to this problem.

Translated by ChatGPT 5