J. Ровно 2k символов

Та же скобочная последовательность $s$, но теперь интересуют только подпоследовательности вида $\underbrace{(\dots(}_{k}\underbrace{)\dots)}_{k}$ — ровно $k$ открывающих и ровно $k$ закрывающих.

Посчитайте их количество.

В классе сумма по всем длинам сворачивалась в один коэффициент. Здесь длина одна, и сворачивать нечего — зато и формула проще.

Первая строка содержит непустую последовательность из символов ( и ) длиной не более $2 \cdot 10^5$.

Вторая строка содержит число $k$ ($1 \le k \le 10^5$).

Одно число — количество таких подпоследовательностей по модулю $10^9 + 7$.