题目描述

如果一个括号序列可以通过添加字符 $+$ 和 $1$ 变成一个合法的数学表达式，则称该括号序列是平衡的。例如，序列 $(())()$、$()$ 和 $(()(()))$ 是平衡的，而 $)($、$(()$ 和 $(()))($ 不是。

子序列是指可以通过删除原序列中的零个或多个元素（不改变剩余元素的顺序）得到的序列。

给定三个整数 $n$、$m$ 和 $k$，请你计算由 $n$ 个左括号 $($ 和 $m$ 个右括号 $)$ 组成的所有序列中，最长平衡子序列的长度恰好为 $2k$ 的序列个数。由于答案可能很大，请对 $1\,000\,000\,007$（$10^9 + 7$）取模。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 3\,000$），表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m, k \le 2\,000$）。

输出格式

对于每个测试用例，输出一个整数，表示满足条件的序列个数。

3
2 2 2
3 2 3
3 2 1

2
0
4

说明/提示

对于第一个测试用例，$()()$、$(())$ 是满足条件的 $2$ 个序列。

对于第二个测试用例，没有满足条件的序列。

对于第三个测试用例，$)((()$、$)(()($、$)()(($、$())(($ 是满足条件的 $4$ 个序列。