#C2023H. 芙莉莲的迷宫之旅

芙莉莲的迷宫之旅

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

题目描述

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

输入格式

输入第一行包含一个整数TT,表示数据组数。

接下来TT行,每行包含三个整数xx,yy,RR。表示迷宫怪的位置 (x,y) (x,y) 和使用的时间RR

输出格式

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

样例输入:

3
1 1 2
1 1 4
15 15 40

样例输出

2
24
218032581

数据范围

对于20%20\%的数据,T10,R10T \le 10,R \le 10

对于40%40\%的数据,T10,R100T \le 10,R \le 100

对于60%60\%的数据,T10,R2×105T \le 10,R \le 2\times 10^5

对于100%100\%的数据,T105,R2×105T \le 10^5,R \le 2\times 10^5231x,y2311-2^{31}\le x,y \le 2^{31}-1