Fibonaccin lukujonossa F_0=0, F_1=1 ja F_n = F_{n-2}+F_{n-1}.

Tehtäväsi on laskea F_n annetulle n:n arvolle.

Syöte

Syötteenä on kokonaisluku n.

Tuloste

Tulosta F_n modulo 10^9+7.

Rajat

• 0 \le n \le 10^{18}

Esimerkki

Syöte:

10

Tuloste:

55