Famil Door and Brackets

## 描述 Family Door 的生日就要到了，Gabi（Family Door的好朋友）想要给他买一个礼物。Gabi决定买一个只包含 '('、')' 的字符串，毕竟 Family Door 最喜欢的字符串是长度为 $n$ 的只包含 '('、')' 的字符串。 我们称一个只包含 '('、')' 的字符串“有效”当且仅当： 1. '('的数量等于')'的数量； 2. 对于该字符串的任意前缀，均满足'('的数量大于等于')'的数量； Gabi 买了一个长度为 $m$ 的只包含 '('、')' 的字符串 $S$。为了使它的长度达到 $n$ ，Gabi要构造两个只包含'('、')'的字符串 $P,Q$，然后将 $P,S,Q$ **顺次**连接得到字符串 $S'$ 。 给出Gabi买的字符串 $S$，要使 $S'$ 有效，Gabi有多少种构造 $P,Q$ 的方案？（$P,Q$都可以为空）。 ## 输入 第一行包括整数 $n,m$；第二行为长度为 $m$ 的字符串 $S$。 ## 输出 输出一个正整数，表示构造 $P,Q$ 的方案数，答案对 $(10^9+7)$ 取模。 ## 数据规模 $1\leq m\leq n\leq 100000,n-m\leq 2000$

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 $ 10^{9}+7 $ .

First line contains $ n $ and $ m $ ( $ 1<=m<=n<=100000,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.

Print the number of pairs of string $ p $ and $ q $ such that $ p+s+q $ is a valid sequence of round brackets modulo $ 10^{9}+7 $ .

4 1
(

4

4 4
(())

1

4 3
(((

0

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.