P6043 「ACOI2020」修学旅行

 第一学期开学没多久，E 班的各位就要去修学旅行了！

现在，六个人 赤羽 業，杉野 友人，奧田 愛美，茅野 楓，神崎 有希子，潮田 渚 为一组，他们将在京都进行一次暗杀旅行。他们的目标仍然是狙击杀老师。政府同时派来了职业狙击手 赤红之眼。但是完成任务的同时，他们想让快乐度尽量的高。 聪明的神崎 有希子（Kanzaki Yukiko）终于求出了快乐度的表达式，令人感到震惊的是，快乐度竟然和旅行景点个数和暗杀杀老师次数有关！ 假设他们经过了 $n$ 个景点，暗杀了 $m$ 次杀老师，且定义： $$ \Gamma(a,b)=\left\{ \begin{aligned} & 1,a>b&\\ & \prod_{i=a}^b i,a \le b&\\ \end{aligned} \right. $$ 那么快乐度为： $$ \sum_{i=0}^m \lgroup \frac{\sqrt{\sum_{j=0}^i (C_i^j)^2C_{n+2i-j}^{2i}}}{\Gamma(n+1,n+i)} \times \Gamma(n-i+1,n) \rgroup $$ **我们保证** $\frac{\sqrt{\sum_{j=0}^i (C_i^j)^2C_{n+2i-j}^{2i}}}{\Gamma(n+1,n+i)} \times \Gamma(n-i+1,n)$ **是一个整数。** 现在他们有 $T$ 个问题想要问你，如果他们经过了 $n$ 个景点并且暗杀 $m$ 次杀老师，能否告诉他们快乐度呢？ **由于答案可能太大，请将答案对 $998244353$ 取模。**

**本题有多组数据**。 第一行一个整数 $T$，表示数据组数。 对于每组数据： 只有一行两个整数 $n$ 和 $m$。

对于每组数据，只有一行一个整数，表示他们经过了 $n$ 个景点，暗杀了 $m$ 次杀老师的快乐度对 $998244353$ 取模后的值。 #### 样例有更新

#### 数据范围 **本题采用捆绑测试**。 - Subtask 1（10 points）：$T \leq 10$，$n,m \leq 10$。 - Subtask 2（20 points）：$T \leq 100$，$n,m \leq 5 \times 10^4$。 - Subtask 3（30 points）：$T \leq 50$，$n,m \leq 9 \times 10^8$。 - Subtask 4（40 points）：数据无特殊限制。 对于 $100\%$ 的数据，$m \leq n$，$1 \leq T \le 10^2$，$1 \leq n,m \leq 9 \times 10^8$。 --- #### 提示 **第三个子任务中的测试点时限 2S，第四个子任务中的测试点时限 5S。**