题目背景

第一学期开学没多久,E 班的各位就要去修学旅行了!
题目描述
现在,六个人 赤羽 業,杉野 友人,奧田 愛美,茅野 楓,神崎 有希子,潮田 渚 为一组,他们将在京都进行一次暗杀旅行。他们的目标仍然是狙击杀老师。政府同时派来了职业狙击手 赤红之眼。但是完成任务的同时,他们想让快乐度尽量的高。
聪明的神崎 有希子(Kanzaki Yukiko)终于求出了快乐度的表达式,令人感到震惊的是,快乐度竟然和旅行景点个数和暗杀杀老师次数有关!
假设他们经过了 n 个景点,暗杀了 m 次杀老师,且定义:
Γ(a,b)=⎩⎨⎧1,a>bi=a∏bi,a≤b那么快乐度为:
i=0∑m⟮Γ(n+1,n+i)∑j=0i(Cij)2Cn+2i−j2i×Γ(n−i+1,n)⟯我们保证 Γ(n+1,n+i)∑j=0i(Cij)2Cn+2i−j2i×Γ(n−i+1,n) 是一个整数。
现在他们有 T 个问题想要问你,如果他们经过了 n 个景点并且暗杀 m 次杀老师,能否告诉他们快乐度呢?
由于答案可能太大,请将答案对 998244353 取模。
输入格式
本题有多组数据。
第一行一个整数 T,表示数据组数。
对于每组数据:
只有一行两个整数 n 和 m。
输出格式
对于每组数据,只有一行一个整数,表示他们经过了 n 个景点,暗杀了 m 次杀老师的快乐度对 998244353 取模后的值。
样例有更新
提示
数据范围
本题采用捆绑测试。
- Subtask 1(10 points):T≤10,n,m≤10。
- Subtask 2(20 points):T≤100,n,m≤5×104。
- Subtask 3(30 points):T≤50,n,m≤9×108。
- Subtask 4(40 points):数据无特殊限制。
对于 100% 的数据,m≤n,1≤T≤102,1≤n,m≤9×108。
提示
第三个子任务中的测试点时限 2S,第四个子任务中的测试点时限 5S。