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 đúng được định nghĩa một cách đệ quy 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)', '[A]', '{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_1~ và ~k_2~ thì ~AB~ cũng là một biểu thức ngoặc đúng 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 và có bậc bằng ~3~.

Ta sẽ xét hai trường hợp sau:

• ~T = 1~: biểu thức ngoặc chỉ gồm kí tự '(' và ')'.
• ~T = 2~: biểu thức ngoặc gồm kí tự '(', ')', '[', ']', '{', '}'.

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 '(' < ')' < '[' < ']' < '{' < '}'.

Yêu cầu: Cho biểu thức ngoặc đúng ~S~, hãy tìm thứ tự của biểu thức ngoặc đúng ~S~.

Input

• Dòng thứ nhất chứa số nguyên ~T~ (~1 \le T \le 2~).
• Dòng thứ hai chứa hai số nguyên ~N~ và ~K~ (~N \le 3000, K \le N/2~).
• Dòng thứ ba chứa ~N~ kí tự của biểu thức ngoặc ~S~.

Output

• Thứ tự của dãy ngoặc ~S~ lấy dư cho ~10^9 + 7~.

Sample Input 1

2
8 4
{}(({}))

Sample Output 1

1008