Farmer John marca normalmente le mucche con un cerchio, ma il ferro è rotto e usa una parentesi (. Ha due razze, Holstein e Guernsey. Ogni mucca porta il segno, che appare parentesi sinistra o destra secondo dove guarda.

Le $N$ mucche sono in fila in direzioni arbitrarie e formano una stringa di parentesi lunga $N$. FJ nota che leggendo solo Holstein da sinistra a destra nel loro ordine ottiene una stringa bilanciata, come per Guernsey! Per sapere se è raro, conta le assegnazioni delle razze alle $N$ mucche con questa proprietà.

Ci sono varie definizioni di “bilanciata”. La più semplice richiede ugual numero totale di ( e ), e in ogni prefisso almeno tante ( quante ). Per esempio, queste stringhe sono bilanciate:

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

queste invece no:

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

Input

• Riga 1: stringa di parentesi lunga $N$ $(1 \le N \le 1000)$.

Output

• Riga 1: un intero, il numero di assegnazioni affinché Holstein e Guernsey formino ciascuna una sottosequenza bilanciata. Può essere grande: stampa il resto per 2012, cioè modulo 2012. Sono valide assegnazioni di una sola razza.

Esempi

Input 1

(())

Output 1

6

Nota

Le seguenti assegnazioni funzionano:

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

Autore del problema: Brian Dean, 2012