Bracket Sequences II.
Su tarea es calcular el número de secuencias de corchetes válidas de longitud cuando se proporciona un prefijo de la secuencia.
Entrada
La primera línea de entrada tiene un número entero .
La segunda línea tiene una cadena de
caracteres: el prefijo de la secuencia.
Salida
Imprime el número de secuencias módulo .
Restricciones
Ejemplo de Entrada
6
(()
Ejemplo de Salida
2
Explicación: Hay dos secuencias posibles: y
.
Comments