Una secuencia de corchetes regular es una cadena de caracteres que consta únicamente de corchetes de apertura y cierre y que satisface las siguientes condiciones:

• Una cadena vacía es una secuencia de corchetes regular.
• Si A es una secuencia de corchetes regular, entonces (A), [A] y {A} también son secuencias de corchetes regulares.
• Si A y B son secuencias de corchetes regulares, entonces AB también es una secuencia de corchetes regular.

Por ejemplo, las secuencias [ ( { } ) ], [ ] ( ) { } y [ { } ] ( )[ { } ] son regulares, pero las secuencias [ ( { { ( [, [] ( { ) } y [ { } ] ) ( [ { } ] no lo son. Alfredo nuestro profe de matemáticas ha encontrado una cadena que parece que podría ser una secuencia de corchetes regular. Algunos de los caracteres se han vuelto borrosos e ilegibles, y podrían haber sido cualquier carácter.

Escriba un programa que calcule de cuántas maneras los caracteres ilegibles en la cadena pueden reemplazarse por corchetes para que el resultado sea una secuencia de corchetes regular. Este número puede ser muy grande, por lo que se deben generar solo sus últimos 5 dígitos.

Entrada

La primera línea contiene un entero par ~N (2 \leq N \leq 200)~, la longitud de la cadena. La segunda línea contiene la cadena. Los caracteres ilegibles se representan con el carácter '?'.

Salida

Salida del número de secuencias de corchetes regulares que la cadena podría haber leído.

Ejemplo de entrada 1

6 ()()()

Ejemplo de salida 1

1

Ejemplo de entrada 2

10 (?([?)]?}?

Ejemplo de salida 2

3

Ejemplo de entrada 3

16 ???[???????]????

Ejemplo de salida 3

92202

Sugerencia

En el segundo ejemplo, las tres secuencias de corchetes regulares coincidentes son ( { ( [ ( ) ] ) } ), ( ) ( [ ( ) ] { } ) y ( [ ( [ ] ) ] { } ).