Cho một dãy ngoặc gồm các loại ngoặc (), [] và {}.

Một dãy ngoặc được coi là đúng nếu:

• Dãy rỗng là dãy ngoặc đúng.
• A, B là dãy ngoặc đúng thì  AB cũng là dãy ngoặc đúng
• A là dãy ngoặc đúng, thì (A), [A], {A} cũng là dãy ngoặc đúng.

Bậc của dãy ngoặc được định nghĩa như sau:

• Dãy rỗng có bậc là 0.
• Giả sử dãy A có bậc là k, thì dãy (A), [A], {A} có bậc là k+1
• Nếu bậc của dãy ngoặc A là k1, B là k2. Thì dãy AB có bậc là max(k1,k2).

Nhiệm vụ của bạn: Cho xâu S độ dài N(N chẵn) chỉ chứa các kí tự ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’ và ‘*’. Cần thay thế vị trí ‘*’ bằng các kí tự  ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’ sao cho dãy S trở thành dãy ngoặc đúng bậc chính xác bằng K. Đếm số cách thay thế được?

Input: Dòng đầu chứa 2 số N và K ( N <= 70).

Dòng 2 chứa xâu S chỉ chứa các kí tự nêu trên.

Output: Số cách tìm được. In kết quả là phần dư cho 10^9 + 7.

Example:

*Trong ví dụ 1, có 3 cách thay là : (()), ([]), ({}).