Su tarea es calcular el número de secuencias de corchetes válidas de longitud ~n~ cuando se proporciona un prefijo de la secuencia.

Entrada

La primera línea de entrada tiene un número entero ~n~. La segunda línea tiene una cadena de ~k~ caracteres: el prefijo de la secuencia.

Salida

Imprime el número de secuencias módulo ~10^9+7~.

Restricciones

• ~1 \leq k \leq n \leq 10^6~

Ejemplo de Entrada

6
(()

Ejemplo de Salida

2

Explicación: Hay dos secuencias posibles: ~(())()~ y ~(()())~.