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.

A string of parentheses is "balanced" if there are the same total number of ('s and )'s, and for any prefix of the string there are at least as many ('s as )'s.

(This problem appeared identically as the Silver problem 3 and Gold problem 1 of the USACO 2012 November contest.)

Line 1: A string of parentheses of length N (1 <= N <= 1000).

A single integer, specifying the number of ways FJ can assign breeds to cows so that the Holsteins form a balanced subsequence of parentheses, and likewise for the Guernseys. Since the answer might be a very large number, please print the number mod 2012. Breed assignments involving only one breed type are valid.

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > November > Silver