Dãy ngoặc

Một dãy ngoặc hợp lệ là một xâu ký tự gồm các ký tự $($, $)$, $[$, $]$, $\{$, $\}$ thỏa mãn:

• Xâu rỗng là dãy ngoặc hợp lệ.
• Nếu $A$ là dãy ngoặc hợp lệ thì $(A)$, $[A]$, $\{A\}$ cũng là dãy ngoặc hợp lệ.
• Nếu $A$ và $B$ là các dãy ngoặc hợp lệ thì $AB$ cũng là dãy ngoặc hợp lệ.

Độ sâu lồng nhau của một dãy ngoặc hợp lệ là số lượng cặp ngoặc lồng nhau nhiều nhất tại bất kỳ vị trí nào trong xâu.

Xét tất cả các dãy ngoặc hợp lệ có độ dài $n$ và độ sâu lồng nhau không quá $k$. Sắp xếp các dãy này theo thứ tự từ điển với quy ước: $($ $<$ $)$ $<$ $[$ $<$ $]$ $<$ $\{$ $<$ $\}$.

Yêu cầu: Cho một dãy ngoặc hợp lệ $S$ có độ dài $n$ và độ sâu lồng nhau không quá $k$, hãy tìm thứ hạng của $S$ trong danh sách trên (đánh số từ $1$).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $k$.
• Dòng thứ hai chứa xâu $S$ có độ dài $n$.

Dữ liệu ra

• Ghi ra một số nguyên duy nhất là thứ hạng của xâu $S$.

Ví dụ