Lần đầu tiên Lan được làm quen với khái niệm biểu thức trong giờ tin học. Cô bé chỉ quan tâm đến việc sẽ nhận được cái gì khi bỏ hết các kí tự khác trong biểu thức ngoại trừ các kí tự ngoặc. Kết quả tìm kiếm trên mạng cho cô biết toán học gọi nó là dãy ngoặc và cô còn biết thêm thế nào là dãy ngoặc đúng.

Ví dụ ()(()) là dãy ngoặc đúng có thể nhận được từ biểu thức toán học chẳng hạn (2+5)(3-(5-9)), còn dãy ngoặc ()(() là một dãy ngoặc không đúng. Lan cũng nhận ra rằng nếu từ một dãy ngoặc đúng nếu thêm vào một dấu ngoặc mở hoặc đóng đều nhận được dãy ngoặc không đúng, nhưng nếu thêm một ngoặc đóng và một ngoặc mở thì có thể nhận được một dãy ngoặc đúng. Ví dụ từ dãy ngoặc đúng (), Lan có thể thêm được ngoặc đúng như sau:

Như vậy dãy ngoặc đúng () ta có 7 cách thêm một ngoặc đóng và một ngoặc mở để được một xâu đúng. Lan muốn biết từ một xâu đúng có thể có bao nhiêu cách thêm một ngoặc đóng và một ngoặc mở để được một xâu ngoặc đúng. Hai cách thêm tại vị trí (i₁, j₁) và (i₂, j₂) được gọi là khác nhau nếu i₁ khác i₂ hoặc j₁ khác j₂.

Dữ liệu cho trong file DAUNGOAC.INP gồm một dòng chứa dãy ngoặc đúng (độ dài không quá 10⁵).

Kết quả ghi ra file DAUNGOAC.OUT gồm một số duy nhất là số cách thêm một ngoặc đóng và một ngoặc mở để nhận được một xâu ngoặc đúng