#660. 回忆京都

回忆京都

题目描述

射命丸文在取材中发现了一个好玩的东西,叫做组合数。

组合数的定义如下:从 nn 个不同元素中,任取 m(m≤n)m(m \leq n) 个元素并成一组,叫做从 nn 个不同元素中取出 mm 个元素的一个组合。所有组合的数量,就是组合数。

组合数的计算公式如下:Cnm=n!m!×(n−m)!\mathrm C^m_n=\dfrac{n!}{m! \times (n-m)!},其中保证 m≤nm \leq n,表示在 nn 个元素中选出 mm 个元素的组合数。

为了方便理解,举一个例子:在 th16.5 秘封噩梦日记的第三周目中,每一天的战斗都有 44 个角色两两组合出场,那么很显然就有 C42=6\mathrm C^2_4=6 种组合方式。

关于这方面的更详细解释,请看样例说明。

由于她对新事物都存在着好奇,因此她想要知道 Cnm\mathrm C^m_n 是多少。这对她来说是个很简单的事情,因此她看了一眼就秒了,因此她决定求出下列式子:

∑i=1n∑j=1mCji\sum_{i=1}^n \sum_{j=1}^m \mathrm C^i_j

其中当 i>ji>j 的时候,钦定 Cji\mathrm C^i_j 为 00。

她也很快就算出来了,不过对自己的答案不是很充满信心,因此你决定帮助她。然而没事找事的她一下子算了 qq 次对于不同的 n,mn,m 的结果,因此这只能劳烦你了。由于你不打算真正地帮助她,你无需把答案对 998244353998244353 取模,也无需对 6412364123 取模,只要告诉她对 1926081719260817 取模之后的答案即可。

输入格式

第一行输入一个非负整数 qq,表示有 qq 次询问。

第二行开始,一共 qq 行,每行两个非负整数 n,mn,m,意思如题所示。

输出格式

一共 qq 行,对于每一个询问,都输出一个答案。

样例

5
2 3
1 4
4 3
2 5
3 5
10
10
11
35
50

题目来源:洛谷 P5239