P7341 "MdOI R4" Phoenix

This is the only problem among the $6$ problems that has no background.

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$.

**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 $T$ lines, each corresponding to one test case. For each test case, output one integer per line indicating the answer.

[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$ | $10$ | | $3$ | No special restrictions | No special restrictions | $a_i \operatorname{or} a_j = \max(a_i, a_j)$ | $10$ | | $4$ | No special restrictions | No special restrictions | Each set contains exactly two elements | $20$ | | $5$ | No special restrictions | $20$ | No special restrictions | $20$ | | $6$ | No special restrictions | No special restrictions | 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