Grid Shuffle

All submissions for this problem are available.
You are given a square grid $G$ with $N$ rows (numbered $1$ through $N$) and $N$ columns (numbered $1$ through $N$). Let's denote the element in the $i$th row and $j$th column by $G_{i, j}$. Initially, for each valid $i, j$, the element $G_{i, j}$ is equal to $i \cdot N+j$. The grid is changing in steps. In one step, either one row or one column of the grid is selected uniformly randomly and then, all the elements in the selected row or column are shuffled uniformly randomly. For a given cell in row $r$ and column $c$, find the probability that after $K$ steps, $G_{r, c}$ is equal to $r \cdot N + c$. It can be proved that this probability can be expressed as an irreducible fraction $p/q$, where $q$ is a positive integer coprime to $998,244,353$. You should compute $p \cdot q^{1}$ modulo $998,244,353$, where $q^{1}$ denotes the multiplicative inverse of $q$ modulo $998,244,353$. ### 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$, $K$, $r$ and $c$. ### Output For each test case, print a single line containing one integer $p \cdot q^{1}\, \%\, 998,244,353$. ### Constraints  $1 \le T \le 5$  $1 \le N, K \le 1,000$  $1 \le r, c \le N$ ### Example Input ``` 2 1 2 1 1 2 1 1 1 ``` ### Example Output ``` 1 249561089 ``` ### Explanation **Example case 1:** Since there is only one row and one column, both with just one element, the grid after each step is the same as the initial grid.Author:  rumblefool 
Tags  rumblefool 
Date Added:  13102019 
Time Limit:  1 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. 