OpenJudge

1126T1:组合

总时间限制:
20000ms
单个测试点时间限制:
2000ms
内存限制:
65535kB
描述

杨辉三角的 第n行第k列 是组合数 C(n,k),代表n个不同元素中选出k个的方案数。注意这里n,k都是从0计数的,并且第0列和n=k对角线上都是1k>n处都为0。杨辉三角中:C(n,k) = C(n-1,k-1) + C(n-1,k),即每个数等于其上方数字和左上方数字之和。



现在sophie站在(n,k) 这个位置上,她向正上方望去,会看到C(n,k)C(n-1,k)C(n-2,k)这些数字,直到遇到边界为止;向左上方望去,会看到C(n,k)C(n-1,k-1)C(n-2,k-2)这些位置,直到遇到边界为止。

sophie想知道向正上方或左上方望去看到的所有数字之和是多少,共 T 组询问。这个数可能很大,你只需将答案对1e9+7 取模即可。


输入
第 1 行一个整数T,表示询问组数。
接下来 T 行,每行三个整数:d n k,其中 d 为 1/2 时表示向上/左上看,(n,k) 为sophie的位置。
输出
T行,对于每组数据,输出1个整数表示答案。
样例输入
3
1 3 2
1 3 5
2 3 2
样例输出
4
0
6
提示
测试点 n,k T
1-4 <=10 =1
5-8 <=1000 =10
9-10 <=5000 =1000
全局题号
16448
添加于
2017-12-03
提交次数
230
尝试人数
45
通过人数
37