题目描述

小 D 正在研究数字序列。

对于一个仅由 0,1 组成的数字序列，小 D 可以在每一步进行如下四种操作之一：

1. 删去最右侧的 0（当然，如果序列中仅有 1，那么无法进行该操作）；
2. 将最右侧的 0 变为 1（当然，与上一条一样，如果序列中仅有 1，那么无法进行该操作）；
3. 在某个右侧没有 0 的位置插入一个 0；
4. 对于某个右侧没有 0 的 1，将其改为 0。

其中，最后两种操作看似有点费解，但它们实际上是前两种操作的逆操作。

小 D 现在有一个长度为 $n$ 的全 1 序列，他想要将其变为长度为 $m$ 的全 1 序列。

小 D 发现这样的操作方案数有无穷多种，于是他想要知道，其中恰好进行 $t$ 步操作的方案个数。

但他并不会，请你帮帮他。因为这个答案可能很大，所以你只要求出答案对 $998244353$ 取模的结果即可。

输入格式

第一行一个整数 $T$，表示小 D 提出的问题个数。

接下来 $T$ 行，每行三个整数 $n,m,t$，表示小 D 的一个问题。

输出格式

输出 $T$ 行，每行一个整数，表示小 D 想要知道的方案数对 $998244353$ 取模的结果。

样例一

输入

10
0 0 4
0 2 4
1 3 4
1 3 6
1 4 6
0 50 150
10 20 20
10 20 100
100 150 200
1000 1500 2000

输出

3
3
9
225
60
695556174
869017219
204568584
850722274
828124570

限制与约定

对于所有测试数据，$T=20$（样例除外），$0\le n,m,t\le 5\times 10^6$。

本题共 25 个测试点，每个 4 分。每个测试点的特殊限制如下：