Fişierul intrare/ieşire:	fibsum.in, fibsum.out	Sursă	Romanian Collegiate Programming Contest 2019
Autor	Radu Visan	Adăugată de	RCPC2019 •RCPC2019
Timp execuţie pe test	0.15 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Fibsum

Se dau T query-uri (left, right) şi se cere calcularea sumei (fib_left + fib_left+1 + ... + fib_right) mod 1 000 000 007 pentru fiecare dintre cele T query-uri, unde fib_i reprezintă al i-lea termen din şirul lui Fibonacci.

Date de intrare

Fişierul de intrare fibsum.in va conţine T linii, fiecare cu 2 numere naturale left şi right, reprezentând intervalele de query.

Date de ieşire

În fişierul de ieşire fibsum.out va conţine T linii, a i-a linie reprezentând răspunsul pentru al i-lea query.

Restricţii

• 1 ≤ T ≤ 10⁴
• 0 ≤ left ≤ right ≤ 10⁹
• fib₀ = fib₁ = 1

Exemplu

Explicaţie

Primii termeni din şirul lui Fibonacci sunt:
fib₀ = 1
fib₁ = 1
fib₂ = 2
fib₃ = 3
fib₄ = 5
fib₅ = 8

Primul query este peste intervalul [3, 5], cu suma 3 + 5 + 8 = 16. Al doilea query este peste intervalul [1, 4], cu suma 1 + 2 + 3 + 5 = 11.

Cum se trimit solutii?