CF629C.Famil Door and Brackets

As Famil Door’s birthday is coming, some of his friends (like Gabi) decided to buy a present for him. His friends are going to buy a string consisted of round brackets since Famil Door loves string of brackets of length n more than any other strings!

The sequence of round brackets is called valid if and only if:

1. the total number of opening brackets is equal to the total number of closing brackets;
2. for any prefix of the sequence, the number of opening brackets is greater or equal than the number of closing brackets.

Gabi bought a string s of length m (m ≤ n) and want to complete it to obtain a valid sequence of brackets of length n. He is going to pick some strings p and q consisting of round brackets and merge them in a string p + s + q, that is add the string p at the beginning of the string s and string q at the end of the string s.

Now he wonders, how many pairs of strings p and q exists, such that the string p + s + q is a valid sequence of round brackets. As this number may be pretty large, he wants to calculate it modulo 109 + 7.

随着 Famil Door 生日的临近，他的一些朋友（例如 Gabi）决定为他买一份礼物。他的朋友们打算购买一个由圆括号组成的字符串，因为 Famil Door 最喜欢长度为 $n$ 的括号字符串，胜过其他任何字符串！

当且仅当满足以下两个条件时，一个圆括号序列被称为合法的：

1. 开括号的总数等于闭括号的总数；
2. 对该序列的任意前缀，开括号的数量均大于或等于闭括号的数量。

Gabi 已经购买了一个长度为 $m$（其中 $m \leq n$）的字符串 $s$，并希望将其补全为一个长度为 $n$ 的合法括号序列。他将选择两个仅由圆括号组成的字符串 $p$ 和 $q$，并将它们与 $s$ 拼接成字符串 $p + s + q$，即把字符串 $p$ 添加到 $s$ 的开头，把字符串 $q$ 添加到 $s$ 的末尾。

现在他想知道：有多少对字符串 $p$ 和 $q$，使得拼接后的字符串 $p + s + q$ 是一个合法的括号序列？由于该数目可能非常大，他希望计算结果对 $10^9 + 7$ 取模的值。

First line contains n and m (1 ≤ m ≤ n ≤ 100 000, n - m ≤ 2000) — the desired length of the string and the length of the string bought by Gabi, respectively.

The second line contains string s of length m consisting of characters '(' and ')' only.

第一行包含 $n$ 和 $m$（$1 ≤ m ≤ n ≤ 100\,000$，且 $n - m ≤ 2000$）—— 分别表示目标字符串的长度，以及 Gabi 所购买的字符串的长度。

第二行包含一个长度为 $m$ 的字符串 $s$，仅由字符 '(' 和 ')' 组成。

Print the number of pairs of string p and q such that p + s + q is a valid sequence of round brackets modulo 109 + 7.

输出满足条件的字符串对 $p$ 和 $q$ 的数量，使得 $p + s + q$ 构成一个合法的圆括号序列，结果对 $10^9 + 7$ 取模。

In the first sample there are four different valid pairs:

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

In the second sample the only way to obtain a desired string is choose empty p and q.

In the third sample there is no way to get a valid sequence of brackets.

在第一个样例中，存在四组不同的合法配对：

1. $p = \text{"("}$，$q = \text{"))"}$
2. $p = \text{"()"}$，$q = \text{")"}$
3. $p = \text{""}$，$q = \text{"())"}$
4. $p = \text{""}$，$q = \text{")()"}$

在第二个样例中，唯一能得到目标字符串的方法是选择空串 $p$ 和空串 $q$。

在第三个样例中，无法得到合法的括号序列。