← 返回题目列表

Codeforces · 1924/D

D. 平衡子序列

中文机器翻译题面 查看原题

如果可以通过添加字符“+”和“1”将括号序列变成有效的数学表达式,则该括号序列称为平衡的。例如,序列 '(())()'、'()' 和 '(()(()))' 是平衡的,而 ')('、'(()' 和 '(()))(' 不是平衡的。

子序列是可以通过删除零个或多个元素而不改变剩余元素的顺序从给定序列导出的序列。

给你三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$。求由 $$$n$$$ '(' 和 $$$m$$$ ')' 组成的序列数,使得最长平衡子序列的长度为 $$$2 \cdot k$$$。由于答案可能很大,请以 $$$1\,000\,000\,007$$$ 为模进行计算($$$10^9 + 7$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 3 \cdot 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n, m, k \le 2 \cdot 10^3$$$)

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入 #1

3
2 2 2
3 2 3
3 2 1

输出 #1

2
0
4

注意

对于第一个测试用例“()()”,“(())”是$$$2$$$序列

对于第二个测试用例,不可能有任何序列。

对于第三个测试用例,“)((()”、“)(()(”、“)()((”、“())((”是 $$$4$$$ 序列。