F. Скобочная подстрока
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана скобочная последовательность $$$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$$$, содержащих «(((» как подстроку.