问题背景

小杨有n对不同的手套，每对手套由左右各一只组成。

小杨想知道从中取出m只手套，m只手套恰好包含k对手套的情况有多少种。

小杨认为两种取法的情况不同，当且仅当两种情况取出的手套中存在不相同的手套（同一对手套的左右手也视为不同的手套）。

问题描述

给定n对手套，每对手套由左右手组成。小杨想知道从中取出m只手套，恰好包含k对手套的情况有多少种。

格式

输入

第一行包含一个正整数t，代表测试数据组数。

接下来是t组测试用例。对于每组测试用例，一共一行。

• 这一行包含三个正整数n, m, k，代表手套数量，取出手套数量和目标对数。

输出

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

样例

输入数据 1

2
5 5 2
5 5 1

输出数据 1

120
0

提示

对于全部数据，保证： 1 ≤ t ≤ 10^5，1 ≤ n ≤ 1000，1 ≤ m ≤ 2×10^5，1 ≤ k ≤ m。