Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Los árboles pueden ser representados en forma de cadenas. Una de las formas más comunes es la siguiente:

• Las hojas se representan como $()$.
• Los otros nodos se representan como $(S_1 S_2 … S_n)$, donde $S_i$ es la cadena que representa al i-esimo nodo.

Por ejemplo el árbol de la figura se puede representar con la cadena $((()())())$.

Fito está jugando con esas cadenas. Él se ha dado cuenta que algunas cadenas se mantienen siendo representaciones válidas de árboles aún cuando se elimine una subcadena (secuencia de caracteres consecutivos). Por ejemplo, quitando la porción subrayada de la cadena $((()\underline{())(}))$, resulta en $((()))$, que representa el árbol de la siguiente figura:

Sin embargo, él no sabe cómo contar la cantidad de formas que hay de hacer esto. Tu tarea es hacer un programa que dada una cadena cuenta cuantas formas hay de eliminar una porción, de forma tal que el resultado siga siendo una cadena que representa un árbol.

Input

Output

Sample test(s)