You are given a string containing only opening and closing brackets “(” and “)” of size m. You have to append 2 strings a and b in the order a+s+b and make them valid string of size n with the following properties,
- At any index, number of opening brackets should be greater than closing brackets
- No. of opening and closing brackets should be equal.
You have to tell number of combinations of string a and b if its possible, otherwise print “0”.
Print the answer with modulo 109 + 7.
Input Format
1st Line: n m 2nd Line: string s
Constraints
1<= m <= n <= 10^5
n-m <= 1200
Output Format
The number of combinations of a and b. Otherwise -1
Sample Input
4 2 ((
Sample Output
1
Explanation
Only 1 possible case a="" , b="))"