#P15842. 序列

序列

题目描述

小 D 正在研究数字序列。

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

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

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

小 D 现在有一个长度为 nn 的全 1 序列,他想要将其变为长度为 mm 的全 1 序列。

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

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

输入格式

第一行一个整数 TT,表示小 D 提出的问题个数。

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

输出格式

输出 TT 行,每行一个整数,表示小 D 想要知道的方案数对 998244353998244353 取模的结果。

样例一

输入

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=20T=20(样例除外),0≤n,m,t≤5×1060\le n,m,t\le 5\times 10^6。

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

测试点 n,m,tn,m,t n=0n=0 t=2m−2nt=2m-2n
1 ≤5\le 5 是 是
2 否
3 是 否
4 否
5 ≤20\le 20 是 是
6 否
7 是 否
8 否
9 ≤200\le 200 是 是
10 否
11,12 是 否
13,14 否
15 ≤2000\le 2000 是
16,17 否
18 ≤106\le 10^6 是
19 否
20 ≤5×106\le 5\times 10^6 是 是
21 否
22,23 是 否
24,25 否