BRACKET - Dãy ngoặc

Giới hạn

• Thời gian: 0.206s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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, 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.

Example

Input:
6 2
(())()

Output:
3
2

---

• Người up: dtmp