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à k₁ và k₂ thì AB cũng là một biểu thức ngoặc đúng có bậc bằng max(k₁, k₂).

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 k 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.