Farmer John zwykle wypala okrągły znak, ale żelazo jest zepsute, więc używa nawiasu (. Ma dwie rasy, Holstein i Guernsey. Każda krowa ma znak nawiasu, który zależnie od kierunku patrzenia wygląda jak lewy lub prawy.
$N$ krów stoi w szeregu w dowolnych kierunkach, tworząc napis nawiasów długości $N$. FJ widzi, że czytając tylko Holstein od lewej do prawej w ich kolejności dostaje zrównoważony napis, tak samo Guernsey! Aby zbadać rzadkość, policz przypisania ras $N$ krowom z tą własnością.
Są różne definicje „zrównoważenia”. Najprostsza wymaga tyle samo ( i ) łącznie, a w każdym prefiksie co najmniej tyle ( co ). Na przykład te napisy są zrównoważone:
() (()) ()(()())
a te nie:
)( ())( ((())))
Wejście
- Wiersz 1: napis nawiasów długości $N$ $(1 \le N \le 1000)$.
Wyjście
- Wiersz 1: liczba całkowita, liczba przypisań, by Holstein i Guernsey każda tworzyła zrównoważony podciąg. Odpowiedź może być duża: wypisz resztę przez 2012, czyli modulo 2012. Przypisania tylko jednej rasy są poprawne.
Przykład
Wejście 1
(())
Wyjście 1
6
Uwagi
Te przypisania są poprawne:
(()) HHHH
(()) GGGG
(()) HGGH
(()) GHHG
(()) HGHG
(()) GHGH
Autor zadania: Brian Dean, 2012