#2287. [GESP202409 八级] 手套配对

[GESP202409 八级] 手套配对

Description

⼩杨有 nn 对不同的⼿套,每对⼿套由左右各⼀只组成。

⼩杨想知道从中取出 mm 只⼿套,mm 只⼿套恰好包含 kk 对⼿套的情况有多少种。

⼩杨认为两种取出的情况不同,当且仅当两种情况取出的⼿套中存在不同的⼿套(同⼀对⼿套的左右⼿也视为不同的⼿套)。

Input Format

第一行包含一个正整数 tt ,代表测试⽤例组数。

接下来是 tt 组测试⽤例。对于每组测试⽤例,⼀共⼀⾏。

第⼀⾏包含三个正整数 nn , mm , kk ,代表⼿套数量,取出的⼿套数和⽬标对数。

Output Format

对于每组测试数据,输出⼀个整数,代表可能的情况数量对 109+710^9+7 取模的结果。

2
5 6 2
5 1 5

120
0

Hint

数据范围

子任务编号 数据点占比 tt nn mm kk
1 30%30\% 5\leq 5 1000\leq 1000 3\leq 3 =1=1
2 30%30 \% 5\leq 5 5\leq 5 10\leq 10 5\leq 5
3 40%40\% 105\leq 10^5 1000\leq 1000 2000\leq 2000 2000\leq 2000

对于全部数据,保证有 1t105,1n10001 \leq t \leq 10^5, 1 \leq n \leq 10001m2×n1 \leq m \leq 2 \times n1kn1 \leq k \leq n

Source

GESP八级202409