Brackets All Over

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,

  1. At any index, number of opening brackets should be greater than closing brackets
  2. 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


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



Only 1 possible case a="" , b="))"