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="))"