Олимпиадный тренинг

Задача . 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\)).

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

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

Примечание

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

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

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


Примеры
№Входные данныеВыходные данные
1
3
2 2 2
3 2 3
3 2 1
2
0
4
Статистика успешных решений по компиляторам
 Кол-во
С++3