Farmer John suele marcar sus vacas con un círculo, pero su hierro está roto y usa un paréntesis (. Hay dos razas, Holstein y Guernsey. Cada vaca lleva la marca, que parece paréntesis izquierdo o derecho según hacia dónde mire.

Las $N$ vacas están en fila en direcciones arbitrarias, formando una cadena de paréntesis de longitud $N$. FJ ve que leer solo Holstein de izquierda a derecha en su orden produce una cadena equilibrada; ¡lo mismo con Guernsey! Para ver si es raro, cuenta las asignaciones de razas a las $N$ vacas con esta propiedad.

Hay varias definiciones de “equilibrada”. La más simple exige igual número total de ( y ), y al menos tantos ( como ) en cualquier prefijo. Por ejemplo, estas cadenas están equilibradas:

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

pero estas no:

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

Entrada

• Línea 1: una cadena de paréntesis de longitud $N$ $(1 \le N \le 1000)$.

Salida

• Línea 1: un entero, el número de asignaciones donde Holstein y Guernsey forman cada una una subsecuencia equilibrada. Puede ser grande: imprime el resto al dividir por 2012, es decir módulo 2012. Asignaciones con una sola raza son válidas.

Ejemplos

Entrada 1

(())

Salida 1

6

Nota

Estas asignaciones funcionan:

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

Autor del problema: Brian Dean, 2012