Последовательность скобок называется сбалансированной, если ее можно превратить в правильное математическое выражение, добавив символы '+' и '1'. Например, последовательности '(())()', '()', и '(()(()))' сбалансированы, в то время как ')(', '(()', и '(()))(' — нет.
Подпоследовательность — это последовательность, которую можно получить из данной последовательности, удалив ноль или более элементов, и не меняя порядок оставшихся элементов.
Даны три целых числа \(n\), \(m\) и \(k\). Найдите количество последовательностей, состоящих из \(n\) '(' и \(m\) ')', таких, что самая длинная сбалансированная подпоследовательность имеет длину \(2 \cdot k\). Поскольку ответ может быть большим, вычислите его по модулю \(1\,000\,000\,007\) (\(10^9 + 7\)).
Примечание
Для первого тестового случая "()()", "(())" — \(2\) последовательности
Для второго тестового случая невозможна ни одна последовательность.
Для третьего тестового случая "))()(", "))(()", ")())(", "()))(" — \(4\) последовательности.