C. Фома Дор и скобки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Фомы Дора скоро день рождения, и его друг Габи решил подготовить ему подарок. Он знает, что Фома Дор без ума от правильных последовательностей из круглых скобок длины ровно n.

Последовательность круглых скобок называется правильной, если выполнены следующие условия:

  1. количество открывающих скобок в последовательности равно количеству закрывающих скобок
  2. для любого префикса последовательности количество открывающих скобок на этом префиксе не меньше количества закрывающих скобок на этом префиксе.

Габи купил строчку s длины m (m ≤ n) и хочет дополнить её до правильной скобочной последовательности длины n. Для этого он выберет какие-то последовательности скобок p и q и получит строку p + s + q, то есть припишет p в начало строки s и q в конец строки s.

Теперь ему интересно, сколько существует пар строк p и q, таких что строка p + s + q является правильной скобочной последовательностью длины n. Вычислите это значение по модулю 109 + 7.

Входные данные

В первой строке входных данных записаны два числа n и m(1 ≤ m ≤ n ≤ 100 000, n - m ≤ 2000) — любимая длина Фомы и длина строки, купленной Габи, соответственно.

Во второй строке записана строка s длины m, состоящая только из символов '(' и ')'.

Выходные данные

Выведите количество пар строк p и q, таких что строка p + s + q является правильной скобочной последовательностью. Не забудьте, что требуется только вывести остаток от деления этого числа на 109 + 7.

Примеры
Входные данные
4 1
(
Выходные данные
4
Входные данные
4 4
(())
Выходные данные
1
Входные данные
4 3
(((
Выходные данные
0
Примечание

В первом примере подходят четыре различные пары:

  1. p = "(", q = "))"
  2. p = "()", q = ")"
  3. p = "", q = "())"
  4. p = "", q = ")()"

Во втором примере единственным способом получить правильную последовательность будет выбрать пустые p и q.

В третьем примере никакие p и q не сделают строчку p + s + q правильной скобочной последовательностью.