== include(page="template/taskheader" task_id="fibsum") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $fibsum.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $fibsum.out$ ...

Î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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 10^5^$
* $0 ≤ left ≤ right ≤ 10^9^$
* $fib{~0~} = fib{~1~} = 1$

h2. Exemplu
table(example). |_. fibsum.in |_. fibsum.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
  3 5
  1 4
| 16
  11

|
h3. Explicaţie

...

Primii termeni din şirul lui Fibonacci sunt:
$fib{~0~} = 1$
$fib{~1~} = 1$
$fib{~2~} = 2$
$fib{~3~} = 3$
$fib{~4~} = 5$
$fib{~5~} = 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$.

== include(page="template/taskfooter" task_id="fibsum") ==