Uolevin matematiikan opettaja antoi vielä toisen tehtävän, mutta tästäkään Uolevi ei selviytynyt. Voisitko auttaa jälleen?

Tehtävässä täytyy laskea $n$ ensimmäisen Fibonaccin luvun summa. Fibonaccin luvut ovat $1, 1, 2, 3, 5, 8, 13, 21, \ldots$

Syöte

Syötteen ainoalla rivillä on kokonaisluku $n$.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: $n$ ensimmäisen Fibonaccin luvun summa. Vastaus voi olla suuri, joten tulosta se modulo $10^9+7$.

Rajat

• $1 \le n \le 10^{18}$

Esimerkki

Syöte:

5

Tuloste:

12

Selitys: $1+1+2+3+5=12$.