平衡子序列

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定 $n,m,k$，求所有恰含 $n$ 个左括号和 $m$ 个右括号的序列中，最长合法括号子序列长度恰为 $2k$ 的序列数量。答案对 $10^9+7$ 取模。

子序列可以通过删除若干字符且不改变剩余字符相对顺序得到。合法括号序列包括 ()、(())()，但不包括 )(、(()。

输入格式

第一行一个整数 $t$。接下来 $t$ 行每行三个整数 $n,m,k$。

输出格式

对每个测试用例输出一行答案。

样例输入

3
2 2 2
3 2 3
3 2 1

样例输出

2
0
4

数据范围

$1\le t\le3000$，$1\le n,m,k\le2000$。

各子任务数据彼此独立计分。