{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"You are given a square grid $G$ with $N$ rows (numbered $1$ through $N$) and $N$ columns (numbered $1$ through $N$). Let\u0027s 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$.\r\n\r\nThe 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.\r\n\r\nFor 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$.\r\n\r\n### Input\r\n- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\r\n- The first and only line of each test case contains four space-separated integers $N$, $K$, $r$ and $c$.\r\n\r\n### Output\r\nFor each test case, print a single line containing one integer $p \\cdot q^{-1}\\, \\%\\, 998,244,353$.\r\n\r\n### Constraints \r\n- $1 \\le T \\le 5$\r\n- $1 \\le N, K \\le 1,000$\r\n- $1 \\le r, c \\le N$\r\n\r\n### Example Input\r\n```\r\n2\r\n1 2 1 1\r\n2 1 1 1\r\n```\r\n\r\n### Example Output\r\n```\r\n1\r\n249561089\r\n```\r\n\r\n### Explanation\r\n**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.\r\n"}}]}