Biểu thức ngoặc là xâu chỉ gồm các kí tự (, ), [, ], {, }. 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 và có bậc bằng \(k\) thì (\(A\)), [\(A\)], {\(A\)} cũng là một biểu thức ngoặc đúng và 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_1\) và \(k_2\) thì \(AB\) cũng là một biểu thức ngoặc đúng là có bậc bằng \(\max(k_1,k_2)\).

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 có bậc bằng \(3\).

Với hai số nguyên \(n,k\), người ta tiến hành tạo ra tất cả các biểu thức ngoặc đúng có độ dài \(n\) và bậc không vượt quá \(k\). Sắp xếp các biểu thức ngoặc theo thứ tự từ điển, chú ý rằng trong bài toán này thứ tự từ điển của các kí tự ngoặc là ( \(<\) ) \(<\) [ \(<\) ] \(<\) { \(<\) }.

Yêu cầu: Cho \(n,k\) và \(S\) là một xâu chỉ gồm các kí tự (, ), [, ], {, }, hãy tìm thứ tự của biểu thức ngoặc đúng \(S\).

Input

• Dòng đầu chứa hai số nguyên \(n,k\) (\(n \le 200, k \le 5\)).
• Dòng thứ hai chứa một xâu \(S\) độ dài \(n\).

Output

• Một dòng chứa một số nguyên là thứ tự của biểu thức ngoặc đúng.

Example

2 1
[]

2