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

Una cadena de paréntesis, llaves y corchetes  se dice que está balanceada si está incluida en alguno de los siguientes casos:

• Es una de las cadenas  () , [] o {} .
• Es la concatenación de dos cadenas balanceadas.
• Es una cadena de la forma ( s ), [s] o {s} donde s es una cadena balanceada.

Fito estaba jugando con una cadena de este tipo, pero de repente, algunos elementos se conviertieron en $?$. Fito quiere que lo ayudemos a contar de cuántas formas él puede sustituir los $?$ por paréntesis, llaves y corchetes de forma tal que las cadenas que obtenga estén balanceadas.

Input

La primera línea de entrada contiene un entero $N$ $(2 \le N \le 200)$ que representa la longitud de la cadena. La segunda línea contiene una cadena que contiene paréntesis, llaves, corchetes  y $?$.

Output

Una línea con un entero que representa la cantidad de formas que tiene Fito de sustituir los $?$. Como la respuesta puede ser muy grande usted debe imprimir solo los ultimos 5 digitos del resultado.

Sample test(s)