Farmer John marca normalmente as vacas com um círculo, mas o ferro está avariado e usa um parêntese (. Há duas raças, Holstein e Guernsey. Cada vaca tem essa marca, que parece parêntese esquerdo ou direito conforme a direção em que olha.

As $N$ vacas estão numa fila em direções arbitrárias, formando uma cadeia de parênteses de comprimento $N$. FJ vê que ler só Holstein da esquerda para a direita pela ordem de ocorrência dá uma cadeia equilibrada; o mesmo para Guernsey! Para ver se é raro, conte as atribuições de raças às $N$ vacas com essa propriedade.

Há várias definições de “equilibrada”. A mais simples exige igual número total de ( e ), e pelo menos tantos ( como ) em qualquer prefixo. Estas cadeias, por exemplo, são equilibradas:

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

mas estas não:

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

Entrada

• Linha 1: cadeia de parênteses de comprimento $N$ $(1 \le N \le 1000)$.

Saída

• Linha 1: inteiro, o número de atribuições em que Holstein e Guernsey formam cada uma uma subsequência equilibrada. Pode ser grande: imprima o resto por 2012, ou seja módulo 2012. Atribuições só de uma raça são válidas.

Exemplos

Entrada 1

(())

Saída 1

6

Nota

As seguintes atribuições funcionam:

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

Autor do problema: Brian Dean, 2012