Tu tarea consiste en calcular el número de maneras de obtener una suma ~n~ lanzando dados. Cada lanzamiento da como resultado un entero entre ~1~ y ~6~.

Por ejemplo, si ~n = 10~, algunas maneras posibles son ~3 + 3 + 4, 1 + 4 + 1 + 4~ y ~1 + 1 + 6 + 1 + 1~.

Entrada

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

Salida

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

Restricciones

• ~1 \leq n \leq 10^{18}~

Ejemplo de Entrada

8

Ejemplo de Salida

125