Farmer John thường đóng dấu những con bò của mình bằng một dấu tròn, nhưng chiếc bàn là đóng dấu của ông đã hỏng nên ông đành đóng lên mỗi con bò một dấu có hình dấu ngoặc (. Trang trại của ông có hai giống bò: Holstein và Guernsey. Ông đóng lên mỗi con bò một dấu có hình dấu ngoặc. Tùy theo hướng con bò đang quay mặt, dấu này có thể trông giống dấu ngoặc mở hoặc dấu ngoặc đóng.

\(N\) con bò của FJ đều đứng thành một hàng, mỗi con quay mặt về một hướng tùy ý, vì vậy các dấu trên chúng trông giống một chuỗi dấu ngoặc có độ dài \(N\). Khi nhìn vào hàng bò này, FJ nhận thấy một quy luật đáng chú ý: nếu ông quét từ trái sang phải chỉ qua các con Holstein (theo thứ tự chúng xuất hiện trong dãy), ông thu được một chuỗi dấu ngoặc cân bằng; hơn nữa, điều tương tự cũng đúng với các con Guernsey! Để xem đây có thực sự là một sự kiện hiếm gặp hay không, hãy giúp FJ tính số cách có thể gán giống cho \(N\) con bò sao cho tính chất này được thỏa mãn.

Có nhiều cách để định nghĩa thế nào là một chuỗi dấu ngoặc "cân bằng". Có lẽ định nghĩa đơn giản nhất là tổng số dấu ( phải bằng tổng số dấu ), và trong mọi tiền tố của chuỗi, số dấu ( phải không ít hơn số dấu ). Ví dụ, các chuỗi sau đều cân bằng:

()
(())
()(()())

trong khi các chuỗi sau thì không:

)(
())(
((())))

Dữ liệu vào

• Dòng 1 chứa một chuỗi dấu ngoặc có độ dài \(N\) (\(1 \le N \le 1000\)).

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất là số cách FJ có thể gán giống cho các con bò sao cho những con Holstein tạo thành một dãy con dấu ngoặc cân bằng và những con Guernsey cũng vậy. Vì đáp án có thể rất lớn, hãy in phần dư của số này khi chia cho \(2012\) (tức là in số đó modulo \(2012\)). Những cách gán chỉ sử dụng một giống bò vẫn hợp lệ.

Ví dụ

(())

6

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

Nguồn

USACO 2012 November Contest, Gold — Problem 1: Balanced Cow Breeds

Tác giả đề: Brian Dean, 2012.