Thuở nhỏ, Dũng rất thông minh trong việc tính toán các biểu thức số học. Dũng tự hỏi điều gì sẽ xảy ra nếu tất cả (trừ dấu ngoặc) bị xóa khỏi biểu thức số học. Với khả năng google search ngay từ thuở nhỏ, Dũng tìm hiểu và thấy rằng các nhà Toán học gọi các dấu ngoặc như vậy là chuỗi ngoặc đúng

Ví dụ ()(()) được gọi là chuỗi ngoặc đúng, thực hiện sau khi xóa mọi thứ và chỉ để lại ngoặc của phép tính (2+2):(3–(5–2)+4), trong khi chuỗi ngoặc (() và ())( không được gọi là chuỗi ngoặc đúng. Từ 3 ngoặc mở và 3 ngoặc đóng, có thể hình thành nên 5 chuỗi ngoặc đúng như sau: ((())), (()()), (())(), ()(()) và ()()().

Với chỉ số IQ không ai sánh bằng, Dũng phát hiện ra rằng việc thêm hai dấu ngoặc vào một chuỗi ngoặc đúng, thì đôi khi, chuỗi ngoặc vẫn giữ nguyên tính chất đúng đấy. Ví dụ, thêm hai dấu ngoặc vào chuỗi  ()()ta sẽ nhận được các chuỗi ngoặc đúng sau: (()()), (())(), ()(()) và ()()(). Dễ dàng thấy rằng, việc thêm hai dấu ngoặc để đảm bảo chuỗi ngoặc đúng, thì một ngoặc sẽ là mở, còn ngoặc còn lại sẽ là đóng.

Dũng muốn đếm số lượng các cách khác nhau để thêm hai dấu ngoặc vào chuỗi ngoặc đúng đã cho để kết quả thu được là chuỗi ngoặc đúng. Thật không may, số này có thể rất lớn trong một số trường hợp. Dũng phân biệt cách thêm hai dấu ngoặc sẽ khác nhau nếu vị trí của hai ngoặc này khác nhau. Ví dụ: ngay khi thêm dấu ngoặc vào chuỗi đơn giản nhất ()sẽ thu được chuỗi ngoặc đúng sau (bôi đậm): ()(), (()), (()), (()), (()), ()(), ()().

Do đó, nếu trong chuỗi kết quả, ngoặc mở thêm vào ở vị trí i và ngoặc đóng thêm vào ở vị trí j, thì  cặp (i1, j1) và (i2, j2) được coi là khác nhau nếu i1 ≠ i2 hoặc j1 ≠ j2.

Cần phải viết một chương trình, cho một chuỗi ngoặc đúng, xác định số lượng các cách khác nhau để thêm hai dấu ngoặc, để kết quả thu dược cũng là một chuỗi ngoặc đúng

Định dạng đầu vào

Tệp đầu vào bao gồm một chuỗi không rỗng chứa chính xác 2n ký tự: n mở và n đóng ngoặc, đảm bảo rằng chuỗi này là một chuỗi đúng

Định dạng đầu ra

Đầu ra cho tệp đầu ra số lượng các cách khác nhau để thêm hai dấu ngoặc vào chuỗi đã cho để thu được chuỗi ngoặc đúng

Ví dụ

.n tối đa là 50000