Dorim să evaluăm eficienţa metroului din Zalău. În acest scop vom nota cu $getTime(Start, End, EntryTime)$ timpul minim necesar pentru a ajunge din staţia $Start$ în staţia $End$ dacă suntem pe peron la secunda $EntryTime$. Pentru a avea o imagine generală a experienţei călătorului obişnuit dorim să calculăm valoarea expresiei:
$Suma(getTime(Start, End, EntryTime), 0 ≤ Start ≤ N - 1, 0 ≤ End ≤ N - 1, 0 ≤ EntryTime ≤ T)$
$Suma(getTime(Start, End, EntryTime), 0 ≤ Start ≤ N - 1, 0 ≤ End ≤ N - 1, 0 ≤ EntryTime ≤ T - 1) modulo (10^9^ + 7)$
h2. Date de intrare
Fişierul de intrare $metrou3.in$ ...
Fişierul de intrare $metrou3.in$ va conţine pe prima sa linie valorile $N A B$. A doua linie va conţine cele $N$ valori ale şirului $D$.
h2. Date de ieşire
În fişierul de ieşire $metrou3.out$ ...
În fişierul de ieşire $metrou3.out$ se va afla o singură valoare reprezentând valoarea sumei cerute *modulo (10^9^ + 7)*.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ N ≤ 100.000$
* $1 ≤ D[i] ≤ 200.000.000$
* $N ≤ T ≤ 200.000.000$
* $0 ≤ A, B ≤ T - 1$
* Dacă $Start = End$ atunci valoarea funcţiei $getTime()$ este $0$.
h2. Exemplu
table(example). |_. metrou3.in |_. metrou3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 3 0 0
1 1 1| 34|
| 4 0 1
1 1 1 1| 120|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="metrou3") ==
