Balanced Cow Breeds

Farmer John usually brands his cows with a circular mark, but his branding iron is broken, so he must instead brand each cow with a parenthesis-shaped mark: (. He has two breeds of cows on his farm: Holsteins and Guernseys. Depending on which direction a cow is facing, its parenthesis-shaped brand looks like either a left parenthesis ( or a right parenthesis ).

FJ's $N$ cows all stand in a row, each facing an arbitrary direction, so the brands read as a string of parentheses of length $N$. Looking at the lineup, FJ notices a remarkable pattern: if he scans left to right through just the Holsteins (in the order they appear), he reads a balanced string of parentheses; and the same holds for the Guernseys.

To see how rare this is, help FJ count the number of ways he could assign a breed to each of his $N$ cows so that this property holds.

A string of parentheses is balanced if it contains equally many ( and ), and every prefix contains at least as many ( as ). For example, these strings are balanced:

• ()
• (())
• ()(()())

while these are not:

• )(
• ())(
• ((())))

The first line contains a string of parentheses of length $N$ ($1 \le N \le 1000$).

Print a single integer: the number of ways FJ can assign breeds so that the Holsteins form a balanced parenthesis subsequence and the Guernseys do too. Because this number can be very large, print it modulo $2012$. Assignments that use only a single breed are valid.

For the input (()), the six valid breed assignments (H = Holstein, G = Guernsey) are:

(())      (())      (())
HHHH      GGGG      HGGH

(())      (())      (())
GHHG      HGHG      GHGH

so the answer for (()) is 6.