Queries on Matrix

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/OCT19/hindi/JIIT.pdf), [Bengali](http://www.codechef.com/download/translated/OCT19/bengali/JIIT.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/OCT19/mandarin/JIIT.pdf), [Russian](http://www.codechef.com/download/translated/OCT19/russian/JIIT.pdf), and [Vietnamese](http://www.codechef.com/download/translated/OCT19/vietnamese/JIIT.pdf) 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 wellknown 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 spaceseparated 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 \le T \le 50$  $1 \le N, M \le 2,000$  $0 \le Z \le N \cdot M$  $1 \le Q \le 10^{18}$ ### Subtasks **Subtask #1 (10 points):** $1 \le N, M, Q \le 300$ **Subtask #2 (40 points):** $1 \le N, M \le 300$ **Subtask #3 (10 points):** $1 \le N, M \le 500$ **Subtask #4 (10 points):** $1 \le N, M \le 600$ **Subtask #5 (10 points):** $1 \le N, M \le 700$ **Subtask #6 (10 points):** $1 \le N, M \le 800$ **Subtask #7 (10 points):** original constraints ### Example Input ``` 2 2 2 2 0 2 2 2 4 ``` ### Example Output ``` 8 8 ``` ### Explanation **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 evenvalued 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.Author:  iamabjain 
Editorial  https://discuss.codechef.com/problems/JIIT 
Tags  fft, hard, iamabjain, maths, oct19, r_64 
Date Added:  11072017 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 