Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

"But I’m no longer the troublemaker you think I am!" - Naruto Uzumaki

Sakshi had a matrix with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$). Initially, all cells of this matrix contained $0$-s. Let's denote a cell in row $r$ and column $c$ by $(r, c)$.

Sakshi is well-known for troubling others. This time, her friends Nikki and Mansi planned to take revenge and teach her a lesson, so they changed her matrix by performing the following operation $Q$ times:
Choose any valid cell $(x, y)$.
Add $1$ to all the cells in row $x$.
Add $1$ to all the cells in column $y$.

Then, Nikki and Mansi challenged Sakshi to find the total number of ways to perform a sequence of $Q$ operations on the initial matrix such that at the end, exactly $Z$ cells in the matrix contain odd integers. Sakshi is not good at math, since she has spent all her life troubling others, so this time, she really needs your help. Help Sakshi count the number of ways. Since the answer may be large, compute it modulo $998,244,353$.

Note: Two ways to perform a sequence of operations are considered different if there is a valid $i$ such that the cell chosen in the $i$-th operation in one sequence is different from the cell chosen in the $i$-th operation in the other sequence. For example, if we choose the cells $(1,1)$ and $(2,2)$ in this order, it is different from choosing the cells $(2,2)$ and $(1,1)$.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains four space-separated integers $N$, $M$, $Q$ and $Z$.

------ Output ------
For each test case, print a single line containing one integer ― the number of ways to perform a sequence of operations modulo $998,244,353$.

------ Constraints ------
$1 ≤ T ≤ 50$
$1 ≤ N, M ≤ 2,000$
$0 ≤ Z ≤ N \cdot M$
$1 ≤ Q ≤ 10^{18}$

------ Subtasks ------
Subtask #1 (10 points): $1 ≤ N, M, Q ≤ 300$

Subtask #2 (40 points): $1 ≤ N, M ≤ 300$

Subtask #3 (10 points): $1 ≤ N, M ≤ 500$

Subtask #4 (10 points): $1 ≤ N, M ≤ 600$

Subtask #5 (10 points): $1 ≤ N, M ≤ 700$

Subtask #6 (10 points): $1 ≤ N, M ≤ 800$

Subtask #7 (10 points): original constraints

----- Sample Input 1 ------
2

2 2 2 0

2 2 2 4
----- Sample Output 1 ------
8

8
----- explanation 1 ------
Example case 1: If we start by choosing the cell $(1, 1)$, the matrix becomes

2 1
1 0

Now we have two options ? we can choose either even-valued cell. If we choose $(1, 1)$ again, the matrix becomes

4 2
2 0

If we choose $(2, 2)$ instead, it becomes

2 2
2 2

For each of the other three possible initial cells, there are also two cells we can choose in the second operation, which is $4 \cdot 2 = 8$ ways in total.

见题面

见题面