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.