Sau khi đã chơi chán chê với những dãy số, ANDY và BOB lại tiếp tục nghĩ ra một trò chơi với các dãy ngoặc đúng. Dãy ngoặc đúng được định nghĩa như sau:

• () là dãy ngoặc đúng.
• C là dãy ngoặc đúng nếu C = (A) hoặc C = AB, với A và B là các dãy ngoặc đúng. Ví dụ: (), (()), ()(), (())(),...

Hai bạn cùng chọn ra một dãy ngoặc đúng bất kì, rồi mỗi người chọn một số dấu ngoặc cho mình. Luật quy định là tất cả các dấu ngoặc đều phải được chọn và mỗi dấu chỉ được chọn bởi một người. Một trong hai người có thể không chọn dấu ngoặc nào, khi đó người còn lại hiển nhiên phải chọn hết tất cả dấu ngoặc.

Sau khi đã lựa chọn xong, cả hai sẽ cùng nhìn dãy ngoặc đúng từ trái qua phải và nhận ra là nếu chỉ nhìn những dấu ngoặc ANDY (A) chọn thì những dấu ngoặc đó tạo thành một dãy ngoặc đúng, nếu chỉ nhìn những dấu ngoặc BOB (B) chọn thì cũng tương tự.

Cả hai rất thích thú với điều đó và muốn biết có tổng cộng bao nhiêu cách chọn khác nhau mà vẫn thỏa mãn như trên, bạn hãy giúp ANDY và BOB nhé.

Yêu cầu: Hãy thực hiện yêu cầu như trên.

Dữ liệu: Gồm một dòng chứa một dãy ngoặc đúng.

Kết quả: In ra số lượng cách chọn thỏa mãn, do kết quả có thể rất lớn nên chỉ cần in ra phần dư của phép chia kết quả cho 2012.

Ví dụ:

Input

(())

Output

6

Ghi chú:

• Có 25% số test ứng với 25% số điểm có: độ dài dãy ngoặc đúng không quá 20.
• Có 75% số test còn lại ứng với 75% số điểm có: độ dài dãy ngoặc đúng không quá 50000.