3734. 组合游戏

单点时限: 1.0 sec

内存限制: 256 MB

“由于天气原因,今天航路会一路颠簸,所有机上的服务将会暂停。”

空乘人员没有了服务的工作,在飞行途中就没有固定的工作安排了。

空乘人员在上一个字母游戏中落败,但她并不服气。她觉得是 Cuber QQ 出了自己擅长的题,她才无法取胜。

于是这一次游戏,由空乘人员来决定游戏。

空乘人员会给出三个数 $n,r,s$ 。

她认为一个集合如果是完美的,必须要满足以下条件:

  • 当且仅当这个集合是集合 ${1,2,3,\cdots,2n-1,2n}$ 的子集;

  • 这个集合包含 $r$ 个不同的奇数和 $s$ 个不同的偶数;

  • 集合中任意挑选两个数,他们都是不相邻的(如果两个数是相邻的,当且仅当他们差的绝对值为 $1$ 或者他们分别是 $1$ 和 $2n$ )。

现在空乘人员询问 Cuber QQ 能不能计算出这样符合要求的完美的集合总数量。

由于数量可能会很大,空乘人员为了不为难 Cuber QQ ,她允许 Cuber QQ 给出的答案对 $1~000~000~007$ 取模。

输入格式

输入第一行包含一个整数 $T(1\leq T\leq 10^5)$ ,表示数据组数。

接下来的 $T$ 行,每行包含三个整数 $n,r,s(1\leq n\leq 10^5,0\leq r,s\leq 10^5,r+s\leq n)$ 。

输出格式

对于每一组数据,输出一行包含一个整数,表示答案。

样例

Input
1
1 1 0
Output
1
Input
2
3 2 0
2 2 0
Output
3
1
Input
2
4 2 1
4 3 1
Output
4
0

14 人解决,33 人已尝试。

15 份提交通过,共有 110 份提交。

6.8 EMB 奖励。

创建: 10 月前.

修改: 9 月,4 周前.

最后提交: 9 月,2 周前.

来源: N/A

题目标签