Biểu thức ngoặc là xâu chỉ gồm các ký tự ( hoặc ). Biểu thức ngoặc đúng và bậc của biểu thức ngoặc được định nghĩa một cách đệ qui như sau:

• Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng 0,
• Nếu A là biểu thức ngoặc đúng có bậc bằng k thì (A) cũng là một biểu thức ngoặc đúng có bậc bằng k+1 ,
• Nếu A và B là hai biểu thức ngoặc đúng và có bậc tương ứng là k1 và k2 thì AB cũng là một biểu thức ngoặc đúng có bậc bằng max(k1, k2) . Ví dụ, ()(()) là một biểu thức ngoặc đúng có bậc bằng 2 còn (()(())) là một biểu thức ngoặc đúng và có bậc bằng 3. Yêu cầu: Cho số nguyên và xâu S là một xâu chỉ gồm các ký tự (, ) và ?, hãy đếm số cách cách thay các ký tự ? trong xâu S thành ký tự ( hoặc ) để nhận được xâu T là biểu thức ngoặc đúng có bậc bằng k .

Input

• Dòng đầu chứa số nguyên dương k ;
• Dòng thứ hai chứa xâu S (độ dài xâu S không vượt quá 200) chỉ gồm các ký tự (, ) và ?.

Output

• Gồm một dòng là số cách thay ký tự ? trong xâu S thành ký tự ( hoặc ) để nhận được xâu T là biểu thức ngoặc đúng có bậc là k.

Sample Input

2 
????(?

Sample Output

1