Los números de Fibonacci se pueden definir de la siguiente manera:

• ~F_0 = 0~
• ~F_1 = 1~
• ~F_n = F_{n-2} + F_{n-1}~

Su tarea consiste en calcular el valor de ~F_n~ para un valor ~n~ dado.

Entrada

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

Salida

Imprima el valor de ~F_n~ módulo ~10^9+7~.

Restricciones

~0 \leq n \leq 10^{18}~

Ejemplo de Entrada

10

Ejemplo de Salida

55