Balanced Parentheses Breed Assignment

Farmer John usually brands his cows with a circular mark. Due to a broken branding iron, he now marks each cow with a parenthesis ( or ) depending on the cow's facing. His N cows are lined up in a row, and the marks form a string of parentheses. Remarkably, if you extract the subsequence of marks corresponding to the Holsteins and, separately, the subsequence corresponding to the Guernseys, both strings are balanced parentheses sequences.

A balanced parentheses sequence is defined as one where the total number of ( equals the number of ), and in every prefix the number of ( is at least the number of ). For example, the following strings are balanced:

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

Given a string consisting only of the characters ( and ), count the number of ways to assign each character a breed label of either H (Holstein) or G (Guernsey) such that if you form two new strings by taking the parentheses marked H and those marked G (in their original order), both strings are balanced. Output the total number of valid assignments modulo \(2012\).

inputFormat

The input consists of a single line containing a non-empty string of characters, each of which is either ( or ). The length of the string is N.

outputFormat

Output a single integer: the number of valid breed assignments such that the subsequences of parentheses corresponding to Holsteins and Guernseys are both balanced, taken modulo \(2012\).

sample

()

2