DAYNGOAC Dãy ngoặc

Người ta định nghĩa đệ qui dãy ngoặc và cấp của dãy như sau:

• Xâu rỗng được gọi là dãy ngoặc cấp 0.
• Nếu S là xâu ngoặc cấp k thì (S) là xâu ngoặc cấp k+1.
• Nếu A, B là các dãy ngoặc thì S = AB là một dãy ngoặc với cấp bằng số lớn hơn trong cấp của A và B.

Định nghĩa này chỉ áp dụng cho những xâu sinh ra theo qui tắc đệ qui trên.

Cho 2 số nguyên dương N và k, gọi S là tập các dãy ngoặc cấp k độ dài N.

1. Cho biết S có bao nhiêu phần tử.

2. Cho một dãy ngoặc thuộc S, hãy cho biết thứ tự từ điển của dãy này trong tập S.

Input

• Dòng đầu ghi 2 số N, k (N chẵn, N ≤ 60, k ≤ n/2 ).
• Dòng hai ghi 1 xâu ngoặc cấp k độ dài N.

Output: Gồm hai dòng, mỗi dòng trả lời 1 yêu cầu theo thứ tự trên.

Input	Output
6 2 (())()	3 2