Codeforces Round 501 (Div. 3) |
---|
Закончено |
Задана скобочная последовательность $$$s$$$ (не обязательно правильная). Скобочная последовательность — это строка, состоящая только из символов '(' и ')'.
Правильная скобочная последовательность — это скобочная последовательность, которая может быть преобразована в корректное арифметическое выражение при помощи вставки символов '1' и '+' между изначальными символами последовательности. Например, скобочные последовательности «()()» и «(())» являются правильными (полученные выражения выглядят следующим образом: «(1)+(1)» и «((1+1)+1)»), а «)(», «(» и «)» — нет.
Ваша задача — посчитать количество правильных скобочных последовательностей длины $$$2n$$$, содержащих заданную скобочную последовательность $$$s$$$ как подстроку (последовательность подряд идущих символов) по модулю $$$10^9+7$$$ ($$$1000000007$$$).
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — половина длины результирующей правильной скобочной последовательности (результирующие последовательности должны иметь длину ровно $$$2n$$$).
Вторая строка входных данных содержит одну строку $$$s$$$ ($$$1 \le |s| \le 200$$$) — строку $$$s$$$, которая должна содержаться как подстрока в каждой из результирующих правильных скобочных последовательностях ($$$|s|$$$ — длина строки $$$s$$$).
Выведите одно целое число — количество правильных скобочных последовательностей, содержащих заданную скобочную последовательность $$$s$$$ как подстроку. Так как это число может быть очень большим, выведите его по модулю $$$10^9+7$$$ ($$$1000000007$$$).
5
()))()
5
3
(()
4
2
(((
0
Все правильные скобочные последовательности, удовлетворяющие ограничениям, описанным выше, для первого тестового примера:
Все правильные скобочные последовательности, удовлетворяющие ограничениям, описанным выше, для второго тестового примера:
В третьем примере не существует правильных скобочных последовательностей длины $$$4$$$, содержащих «(((» как подстроку.
Название |
---|