406647: GYM102471 B Black and White

Master Pang walks from the bottom-left corner of a $$$n\times m$$$ chessboard to the top-right corner. The chessboard contains $$$n+1$$$ horizontal line segments and $$$m+1$$$ vertical line segments. The horizontal line segments are numbered from $$$0$$$ to $$$n$$$ from bottom to top and the vertical ones are numbered from $$$0$$$ to $$$m$$$ from left to right. The intersection of horizontal line segment $$$r$$$ and vertical segment $$$c$$$ is denoted by $$$(r,c)$$$. The bottom-left corner is $$$(0, 0)$$$ and the top-right corner is $$$(n, m)$$$. At each step, he can only walk from $$$(x, y)$$$ to $$$(x, y+1)$$$ or from $$$(x, y)$$$ to $$$(x + 1, y)$$$.

Each of the $$$n\times m$$$ cells is colored white or black. A cell with corners $$$(i,j), (i+1,j), (i,j+1), (i+1,j+1)$$$ $$$(0\le i<n, 0\le j<m)$$$ is colored white if and only if $$$i\equiv j\pmod 2$$$.

Given $$$Pang$$$'s walking path from $$$(0, 0)$$$ to $$$(n, m)$$$, his score is $$$a-b$$$ where $$$a$$$ is the number of white cells to the left of his walking path and $$$b$$$ is the number of black cells to the left of his walking path.

Help Master Pang count the number of walking paths with score $$$k$$$ modulo $$$998244353$$$.

The first line contains a single integer $$$T$$$ — the number of test cases ($$$1\le T \le 100$$$).

Each of the next $$$T$$$ lines contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1\le n\le 100000, 1\le m\le 100000, -100000\le k\le 100000$$$).

For each test case, output a single integer — the answer modulo $$$998244353$$$.

5
1 1 0
1 1 -1
2 2 1
2 2 0
4 4 1

1
0
1
4
16