Fişierul intrare/ieşire:	metrou3.in, metrou3.out	Sursă	Algoritmiada 2015, Runda 3
Autor	Adrian Budau	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Metrou3

Problema aceasta este despre metroul din Cluj. Glumim, bineînţeles, nu există metrou în Cluj. E de fapt vorba de Zalău. Metroul din Zalău este un ciclu cu N staţii, distanţa între două staţii consecutive nefiind constantă. Aceste distanţe vă sunt date prin şirul D: valorea D[i] reprezintă durata parcurgerii distanţei dintre staţia i şi staţia (i + 1) modulo N în secunde. Fie T durata unui tur complet al metroului (egală cu suma valorilor din D). Ştim că există doar două trenuri: unul care se va afla în staţia 0 în secunda A, mergând în direcţia staţiei 1 şi unul care se va afla în staţia 0 în secunda B şi merge în direcţia staţiei N - 1. Secundele A şi B sunt nişte momente oarecare în care trenurile se află în staţia 0. Ele se vor afla în staţia 0 şi în momentele A + k * T, respectiv B + k * T, pentru orice k întreg. Cu alte cuvinte, trenurile au circulat dintotdeauna şi vor circula pentru totdeauna.

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 - 1) modulo (10⁹ + 7)

Date de intrare

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.

Date de ieşire

În fişierul de ieşire metrou3.out se va afla o singură valoare reprezentând valoarea sumei cerute modulo (10⁹ + 7).

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.

Exemplu

Cum se trimit solutii?