首页 > 试题广场 >

造一造

[编程题]造一造
  • 热度指数：1 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
WYF正试图用一个栈来构造一棵树，现在他已经构造了n个元素作为树的节点，只要将这n个元素依次入栈出栈就可以形成一棵树了。当然，这个问题与树并没有关系，所以它叫做WYF的栈。每次你可以入栈一个新元素或者当栈非空时出栈一个元素，n个元素必须依次入栈，而WYF希望其中第m个元素入栈之后，栈中恰好有k个元素，现在他想知道一共有多少种入栈出栈顺序满足这个条件。

输入描述:
第一行一个正整数T，表示数据组数。(1<=T<=10000)
对于每组数据包含一行三个正整数n,m,k。


输出描述:
 对于每组数据输出一个正整数表示答案。
 由于答案可能过大，所以只需要输出对109+7取模后的答案

示例1

输入

2
3 3 3
3 3 2

输出

1
2
示例2

输入

5
10 3 2
10 2 2
10 7 5
10 6 2
10 7 6

输出

6864
11934
2200
3780
924
示例3

输入

2
5 4 4
5 2 1

输出

5
14

备注:
1<=n,m,k<=106
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

组合数学
上传者：牛客301599号
难度：
0条回答 10浏览

热门推荐

通过挑战的用户

查看代码

相关试题

造一造

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号