#3017. [Usaco2012 Nov]Cow Breeds

题目描述

Farmer John usually brands his cows with a circular mark, but his branding iron is broken, so he instead must settle for branding each cow with a mark in the shape of a parenthesis -- (. He has two breeds of cows on his farm: Holsteins and Guernseys. He brands each of his cows with a parenthesis-shaped mark. Depending on which direction the cow is facing, this might look like either a left parenthesis or a right parenthesis.
FJ's N cows are all standing in a row, each facing an arbitrary direction, so the marks on the cows look like a string of parentheses of length N. Looking at this lineup, FJ sees a remarkable pattern: if he scans from left to right through just the Holsteins (in the order they appear in the sequence), this gives a balanced string of parentheses; moreover, the same is true for the Guernseys! To see if this is truly a rare event, please help FJ compute the number of possible ways he could assign breeds to his N cows so that this property holds.
There are several ways to define what it means for a string of parentheses to be "balanced". Perhaps the simplest definition is that there must be the same total number of ('s and )'s, and for any prefix of the string, there must be at least as many ('s as )'s. For example, following strings are all balanced:
()
(())
()(()())
while these are not:
)(
())(
((())))

()是合法的；
A是合法的，则(A)是合法的；
AB都是合法的，则AB是合法的。

输入格式

一个长度为n的括号序列。

输出格式

不同的编号方式对2012取模后的值。

样例输入

``````

(())
``````

样例输出

``````

6

(())
HHHH
(())
GGGG
(())
HGGH
(())
GHHG
(())
HGHG
(())
GHGH

对于100%的数据满足：1 <= n <= 1,000。``````