Farmer John marque normalement les vaches d’un cercle, mais son fer est cassé : il utilise une parenthèse (. Il a deux races, Holstein et Guernsey. Chaque vache porte cette marque, qui ressemble à une parenthèse gauche ou droite selon son orientation.

Les $N$ vaches sont en ligne dans des directions quelconques, formant une chaîne de parenthèses de longueur $N$. FJ remarque qu’en lisant de gauche à droite seulement les Holstein, dans leur ordre, la chaîne est équilibrée ; pareil pour les Guernsey ! Pour savoir si c’est rare, comptez les façons d’attribuer les races aux $N$ vaches avec cette propriété.

Il existe plusieurs définitions d’« équilibrée ». La plus simple : autant de ( que de ) au total, et dans chaque préfixe au moins autant de ( que de ). Par exemple, ces chaînes sont équilibrées :

()
(())
()(()())

mais pas celles-ci :

)(
())(
((())))

Entrée

• Ligne 1 : une chaîne de parenthèses de longueur $N$ $(1 \le N \le 1000)$.

Sortie

• Ligne 1 : un entier, le nombre d’attributions pour que Holstein et Guernsey forment chacun une sous-séquence équilibrée. Le nombre peut être grand : affichez son reste par 2012, donc modulo 2012. Les attributions d’une seule race sont valides.

Exemples

Entrée 1

(())

Sortie 1

6

Remarque

Les attributions suivantes conviennent :

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

Auteur du problème : Brian Dean, 2012