手套配对：计算从n对手套中取m只恰好包含k对的方案数

时间限制

1.0 s

内存限制

512.0 MB

题面描述

小杨有n对不同的手套，每对手套由左右各一只组成。求从中取出m只手套，恰好包含k对手套的情况有多少种。 两种取出情况不同的判定标准：当且仅当两种情况取出的手套中存在不同的手套（同一对手套的左右手也视为不同的手套）。

输入格式

第一行包含一个正整数 t，代表测试用例组数。 接下来是t组测试用例，每组测试用例占一行，包含三个正整数 n, m, k，分别代表手套总对数、取出的手套数、目标配对数。

输出格式

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

样例输入

2
5 6 2
5 1 5

样例输出

120
0

数据范围

• 通用范围：$1 \leq t \leq 10^5$，$1 \leq n \leq 1000$，$1 \leq m \leq 2n$，$1 \leq k \leq n$
• 子任务划分： | 子任务编号 | 数据点占比 | t | n | m | k | | --- | --- | --- | --- | --- | --- | | 1 | 30% | $\leq 5$ | $\leq 1000$ | $\leq 3$ | $=1$ | | 2 | 30% | $\leq 5$ | $\leq 5$ | $\leq 10$ | $\leq 5$ | | 3 | 40% | $\leq 10^5$ | $\leq 1000$ | $\leq 2000$ | $\leq 2000$ |