本题与芙莉莲的迷宫之旅的区别仅在于移动只能在第一象限中，以及本题的数据范围为 $ T \le 10^3,R \le 2\times 10^3, 0 \le x, y \le 2^{31}-1$ 。

题目描述

芙莉莲又来到了一个宽广的迷宫里，这个迷宫只存在于二维坐标系的 第一象限 中，但是无限大。芙莉莲所在的迷宫入口在平面上的 $(0,0)$ 点。此时芙莉莲看到在迷宫的 $(x,y)$ 位置有一个宝箱怪，于是迫不及待地想要投入宝箱怪的怀抱。芙莉莲每一秒可以往上下左右四个方向中的一个移动一个单位的距离。芙莉莲想知道有多少种移动方法可以用恰好$R$秒从迷宫入口移动到宝箱怪的位置。

输入格式：

输入第一行包含一个整数$T$，表示数据组数。 接下来$T$行，每行包含三个整数$x$,$y$,$R$。表示迷宫怪的位置 $(x,y)$ 和使用的时间$R$。

输出格式：

输出包含$T$行，每行一个整数，表示合法的移动序列数量对998,244,353取模的结果。

样例输入：

3
1 1 2
1 1 4
15 15 40

样例输出：

2
16
333639927

数据范围

对于$20\%$的数据，$T \le 10,R \le 10$。

对于$40\%$的数据，$T \le 10,R \le 100$。

对于$60\%$的数据，$T \le 10,R \le 2\times10^3$。

对于$100\%$的数据，$T \le 10^3,R \le 2\times10^3, 0 \le x, y \le 2^{31}-1$。

提示

注意！迷宫只在第一象限里。

本题与上题无严格的难易度关系。