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

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≤T≤2~).
• Dòng thứ hai chứa hai số nguyên ~N~ và ~K~ (~N≤3000, K≤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

2
8 4
{}(({}))

Sample output

1008

Subtask

• Subtask 1 (20% số điểm): ~T=2,N ≤ 10.~
• Subtask 2 (20% số điểm): ~T = 1,S = ()()()...~
• Subtask 3 (20% số điểm): ~T = 2,S = {}{}{}...~
• Subtask 4 (20% số điểm): ~T = 1.~
• Subtask 5 (20% số điểm): ~T = 2.~