Giống bò cân bằng (Khó)

Cho chuỗi $N$ dấu ngoặc. Gán mỗi ký tự cho một trong hai giống bò (H hoặc G). Đếm số cách gán sao cho chuỗi con của giống H và chuỗi con của giống G đều là chuỗi ngoặc hợp lệ. Kết quả lấy modulo $2012$.

Chuỗi ngoặc hợp lệ: số ( bằng số ), và mọi tiền tố đều có số ( $\ge$ số ).

Dữ liệu vào

Một dòng chứa chuỗi dấu ngoặc độ dài $N$.

Dữ liệu ra

Một số nguyên — số cách gán modulo $2012$.

Ràng buộc

• $1\le N\le 1000$

Ví dụ