You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

本题与芙莉莲的第二次迷宫之旅的区别仅在于移动能在整个二维坐标平面中，以及本题的数据范围为 $T \le 10^5,R \le 2\times 10^5$ 。

题目描述

芙莉莲来到了一个宽广的迷宫里，迷宫可以看成无限大的二维平面。芙莉莲所在的迷宫入口在平面上的 $(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
24
218032581

数据范围

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

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

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

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