D. Сбалансированные подпоследовательности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность скобок называется сбалансированной, если ее можно превратить в правильное математическое выражение, добавив символы '+' и '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$$$).

Выходные данные

Для каждого тестового случая выведите одно целое число — ответ на задачу.

Пример
Входные данные
3
2 2 2
3 2 3
3 2 1
Выходные данные
2
0
4
Примечание

Для первого тестового случая "()()", "(())" — $$$2$$$ последовательности

Для второго тестового случая невозможна ни одна последовательность.

Для третьего тестового случая "))()(", "))(()", ")())(", "()))(" — $$$4$$$ последовательности.