Фермер Джон обычно помечает своих коров круглой меткой, но сейчас его пометочная машина сломалась, и он решил помечать коров отметкой в форме скобок. У него есть две породы коров Holsteins и Guernseys. Каждую породу он помечает меткой в виде скобки. В зависимости от того, В какую сторону корова смотрит, скобка может выглядеть как левая или как правая.
N коров фермера Джона стоят в ряд, каждая смотрит в произвольном направлении, поэтому мы получаем строку скобок длиной N. Глядя на нее, ФД обнаружил, что если смотреть слева направо, то только для коров Holsteins (в порядке, в котором они появились в последовательности), Получится сбалансированная последовательность скобок, однако то же самое верно и для Guernseys! Чтобы выяснить, насколько это редкое событие, Помогите ФД вычислить количество различных способов, которыми можно назначить породы этим N коровам, чтобы выполнялось такое свойство.
Есть несколько способов определить сбалансированную строку. Один из них такой: Строка должна иметь одинаковое количество левых и правых скобок. И для любого префикса строки количество левых скобок должно быть не меньше, чем количество правых скобок.
Например, следующие последовательности скобок сбалансированные:
() (()) ()(()())
А эти - нет.
)( ())( ((())))
PROBLEM NAME: bbreeds
Формат входных данных
* Строка 1: Строка скобок длины N (1 <= N <= 1000).
Формат выходных данных
* Строка 1: Одно целое число - количество способов назначить породы так, чтобы Holsteins формировали сбалансированную последовательность скобок и аналогично Guernseys. Поскольку ответ может быть очень большим, выведите остаток от его деления на 2012. Корректным считается использование только одного типа породы.
Примечание Вот корректные назначения пород (()) HHHH
(()) GGGG
(()) HGGH
(()) GHHG
(()) HGHG
(()) GHGH
Примеры
| № | Входные данные | Выходные данные |
|
1
|
(())
|
6
|