Su tarea es calcular el número de secuencias de corchetes válidas de longitud ~n~. Por ejemplo, cuando ~n=6~, hay 5 secuencias:

()()()
()(())
(())() 
((()))
(()())

Entrada

La única línea de entrada tiene un número entero ~n~.

Salida

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

Restricciones

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

Ejemplo de Entrada

6

Ejemplo de Salida

5