Farmer John thường đóng dấu tròn lên bò, nhưng dụng cụ hỏng nên dùng dấu ngoặc (. Có hai giống Holstein và Guernsey. Mỗi bò mang dấu đó, trông như ngoặc trái hay phải tùy hướng nó quay.

$N$ bò đứng thành hàng với hướng tùy ý, tạo xâu ngoặc dài $N$. FJ thấy đọc riêng Holstein từ trái sang phải theo thứ tự xuất hiện cho xâu cân bằng, Guernsey cũng vậy! Để biết có hiếm không, đếm cách gán giống cho $N$ bò để có tính chất này.

Có nhiều định nghĩa “cân bằng”. Đơn giản nhất là tổng số ( và ) bằng nhau và trong mọi tiền tố số ( không ít hơn ). Ví dụ các xâu này cân bằng:

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

còn các xâu này không:

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

Dữ liệu vào

• Dòng 1: xâu ngoặc dài $N$ $(1 \le N \le 1000)$.

Dữ liệu ra

• Dòng 1: một số nguyên, số cách gán giống để Holstein và Guernsey mỗi giống tạo dãy con ngoặc cân bằng. Đáp án có thể rất lớn, in phần dư chia 2012, tức modulo 2012. Gán chỉ một giống cũng hợp lệ.

Ví dụ

Dữ liệu vào 1

(())

Dữ liệu ra 1

6

Ghi chú

Các cách gán sau hợp lệ:

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

Tác giả bài toán: Brian Dean, 2012