Tu tarea es contar la cantidad de formas de obtener una suma n lanzando un dado una o más veces. Cada lanzamiento produce un resultado entre 1 y 6.

Por ejemplo, si n=3, existen 4 formas:

• \(1+1+1\)
• \(1+2\)
• \(2+1\)
• \(3\)

Entrada

La única línea de entrada contiene un entero (\(1 \leq n \leq 10^6\)).

Salida

Imprime la cantidad de formas módulo (10^9 + 7).

Ejemplo

Entrada

3

Salida

4