Farmer John обычно ставит круглое клеймо, но инструмент сломался, и приходится ставить каждой корове клеймо в виде скобки (. На ферме две породы: Holstein и Guernsey. Скобка на каждой корове выглядит левой или правой в зависимости от того, куда она смотрит.
$N$ коров стоят в ряд в произвольных направлениях, и клейма образуют строку скобок длины $N$. FJ замечает: если слева направо читать только Holstein в порядке появления, строка сбалансирована; то же верно для Guernsey! Чтобы выяснить редкость события, посчитайте способы назначить породы $N$ коровам с этим свойством.
Определений баланса несколько. Простейшее: общее число ( и ) одинаково, а в любом префиксе ( не меньше, чем ). Например, эти строки сбалансированы:
() (()) ()(()())
а эти нет:
)( ())( ((())))
Входные данные
- Строка 1: строка скобок длины $N$ $(1 \le N \le 1000)$.
Выходные данные
- Строка 1: целое число способов назначить породы, чтобы подпоследовательности Holstein и Guernsey обе были сбалансированы. Ответ велик, выведите остаток при делении на 2012, то есть по модулю 2012. Назначения только одной породы допустимы.
Примеры
Входные данные 1
(())
Выходные данные 1
6
Примечание
Подходят следующие назначения пород:
(()) HHHH
(()) GGGG
(()) HGGH
(()) GHHG
(()) HGHG
(()) GHGH
Автор задачи: Brian Dean, 2012