Description

$\textit{Master Pang}$ 从一个 $n\times m$ 的棋盘的左下角走到右上角。棋盘包含 $n+1$ 条水平线段和 $m+1$ 条竖直线段。水平线段自下而上编号为 $0$ 到 $n$，竖直线段自左而右编号为 $0$ 到 $m$。水平线段 $r$ 与竖直线段 $c$ 的交点记作 $(r,c)$。左下角为 $(0, 0)$，右上角为 $(n, m)$。每一步，他只能从 $(x, y)$ 走到 $(x, y+1)$ 或 $(x, y)$ 走到 $(x+1, y)$。

棋盘上的每个单元格都是白色或黑色。一个以 $(i,j), (i+1,j), (i,j+1), (i+1,j+1)$ 为顶点的单元格（$0\le i<n, 0\le j<m$）当且仅当 $i\equiv j\pmod 2$ 时为白色。

给定 $Pang$ 从 $(0, 0)$ 走到 $(n, m)$ 的一条路径，他的得分为 $a-b$，其中 $a$ 是路径左侧的白色单元格数量，$b$ 是路径左侧的黑色单元格数量。

请你帮助 $\textit{Master Pang}$ 计算得分为 $k$ 的路径数量，对 $998244353$ 取模。

Input Format

第一行包含一个整数 $T$，表示测试用例数量（$1\le T \le 100$）。

接下来的 $T$ 行，每行包含三个整数 $n$、$m$ 和 $k$（$1\le n\le 100000, 1\le m\le 100000, -100000\le k\le 100000$）。

Output Format

对于每个测试用例，输出一个整数，表示答案对 $998244353$ 取模后的结果。

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

1
0
1
4
16

Hint

由 ChatGPT 4.1 翻译