CSES - Toinen tehtävä
  • Time limit: 2.00 s
  • Memory limit: 512 MB
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$.