Su tarea consiste en contar el número de formas de construir la suma ~n~ lanzando un dado una o más veces. Cada lanzamiento produce un resultado entre ~1~ y ~6~.

Por ejemplo, si ~n=3~, hay ~4~ maneras:

1+1+1
1+2
2+1 
3

Entrada

La única línea de la entrada contiene un entero ~n~.

Salida

Escriba el número de formas módulo ~10^9+7~.

Restricciones

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

Ejemplo de Entrada

3

Ejemplo de Salida

4