Farmer John brandmarkt Kühe gewöhnlich mit einem Kreis. Sein Eisen ist kaputt, also verwendet er eine Klammer (. Er hat Holstein und Guernsey. Jede Kuh trägt die Klammermarke, die je nach Blickrichtung wie eine linke oder rechte Klammer aussieht.

Die $N$ Kühe stehen in einer Reihe mit beliebigen Blickrichtungen und bilden eine Klammerfolge der Länge $N$. FJ bemerkt: Nur die Holstein von links nach rechts in Reihenfolge gelesen ergeben eine ausgeglichene Folge, ebenso die Guernsey! Um die Seltenheit zu untersuchen, zähle Rassenzuweisungen zu $N$ Kühen mit dieser Eigenschaft.

Es gibt mehrere Definitionen für „ausgeglichen“. Die einfachste fordert gleich viele ( und ) insgesamt und in jedem Präfix mindestens so viele ( wie ). Beispielsweise sind diese Folgen ausgeglichen:

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

diese hingegen nicht:

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

Eingabe

• Zeile 1: eine Klammerfolge der Länge $N$ $(1 \le N \le 1000)$.

Ausgabe

• Zeile 1: eine ganze Zahl für die Zuweisungen, bei denen Holstein und Guernsey jeweils eine ausgeglichene Teilfolge bilden. Die Zahl kann groß sein: Gib den Rest durch 2012, also modulo 2012 aus. Zuweisungen nur einer Rasse sind gültig.

Beispiele

Eingabe 1

(())

Ausgabe 1

6

Hinweis

Folgende Zuweisungen funktionieren:

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

Autor der Aufgabe: Brian Dean, 2012