P5159 WD and Matrices

WD spends all day immersed in matrices and cannot get out of it.

WD likes matrices very much, especially 01 matrices. One day, CX gave WD a huge $n$-row, $m$-column 01 matrix. WD found that the XOR value of every row and every column of this matrix is $0$. CX then asked, “WD, do you know how many 01 matrices have XOR value $0$ in every row and every column!?” WD of course does not know this, so he came to ask you. Since the answer may be very large, you only need to output the result modulo $998\,244\,353$.

The first line contains an integer $T$, which represents the number of test cases. In the next $T$ lines, each line contains two integers $n, m$, representing the number of rows and columns in the query.

Output $T$ lines. Each line contains one integer, the answer modulo $998\,244\,353$.

- Subtask 1 (11 pts): $1\le T\le 10,~1\le n,m\le 4$. - Subtask 2 (43 pts): $1\le T\le 5,~1\le n\le 5,~1\le m\le 1,000$. - Subtask 3 (46 pts): $1\le T\le 10^5,~1\le n,m\le 10^9$. Translated by ChatGPT 5