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