Recientemente, los concursantes han estado competiendo con cadenas de paréntesis balanceados y comparándolas entre sí para ver quién tiene la mejor.

A tales cadenas se les asigna un puntaje como sigue (todas las cadenas son balanceadas): la cadena \("()"\) tiene puntaje 1; si \("A"\) tiene puntaje ~s(A)~ entonces \("(A)"\) tiene puntaje ~2*s(A)~; y si \("A"\) y \("B"\) tienen puntajes ~s(A)~ y ~s(B)~, respectivamente, entonces \("AB"\) tiene puntaje ~s(A)+s(B)~. Por ejemplo, \(s("(())()") = s("(())") + s("()") = 2*s("()")+1 = 2*1+1 = 3\).

Jorge quiere derrotar a todos sus compañeros concursantes, por lo tanto necesita calcular el puntaje de algunas cadenas. Dada una cadena de paréntesis balanceados de longitud ~N (2 \leq N \leq 100,000)~, ayude a Jorge a calcular su puntaje.

FORMATO DE ENTRADA:

• Línea 1: Un solo entero: ~N~

• Líneas 2..N + 1: La línea ~i+1~ contendrá un entero: ~0~ si el i-ésimo carácter de la cadena es ~'('~, y 1 si el i-ésimo carácter de la cadena es ~')'~

FORMATO DE SALIDA:

• Línea 1: El puntaje de la cadena. Como este número puede ser bastante grande, dé el puntaje módulo 12345678910.

ENTRADA EJEMPLO

6
0
0
1
1
0
1

SALIDA EJEMPLO

3

DETALLES DE LA ENTRADA:

Esto corresponde a la cadena \("(())()"\).

DETALLES DE LA SALIDA:

Como se discutió anteriormente.