Fişierul intrare/ieşire:	peru.in, peru.out	Sursă	RMI 2020 Ziua 1
Autor	Alexandru Petrescu	Adăugată de	Mihai-Cristian Popescu •mihai50000
Timp execuţie pe test	0.55 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Peru

Azi dimineaţă, Roxy a găsit N gândaci pe birou. Ei sunt numerotaţi de la 0 la N - 1 şi fiecare gândac i are puterea S_i. Roxy vrea să strivească gândacii pentru a-şi, face tema la matematică. Pentru asta, a cumpărat o mănuşă specială pe care o poate folosi pentru a lovi o subsecvenţă continuă de K gândaci. Dacă Roxy face un efort E, atunci acei gândaci a căror putere S_i este mai mică sau egală cu E vor fi strivitţi, în timp ce toţi ceilalţi vor rămâne nevătămaţi. Gândacii striviţi îşi menţin poziţiile pe birou. Roxy poate folosi mănuşa de câte ori doreşte.
Roxy vrea să ştie dacă tu poţi calcula efortul minim necesar pentru a strivi primii i gândaci pentru fiecare 1 ≤ i ≤ N. Pentru că sunt prea multe numere, Roxy doreşte să-i dai rezultatul expresiei următoare: X₀ * 23^N-1 + X₁ * 23^N-2 + ... + X_N-1 modulo 10⁹ + 7, unde X_i reprezintă efortul minim total pentru a strivi primii i + 1 gândaci.

Date de intrare

Fişierul de intrare peru.in contine pe prima linie T, numarul de gandaci.
Urmatoarele 2 * T linii contin descrierea testelor, cate doua linii pentru fiecare test:
Prima linie contine N si K, iar a doua linie contine vectorul R de lungime N.

Date de ieşire

În fişierul de ieşire peru.out contine T linii, pe linia i aflandu-se raspunsul pentru al i-lea test.

daca sirul e d1, d2, ..., dn, raspunsul se calculeaza asa:
int ans = 0; for (int i = 1; i <= n; i++) ans = (23LL * ans + di) % 1000000007.

Restricţii

• 1 ≤ N ≤ 2500000

• 1 ≤ K ≤ N

• 1 ≤ S_i ≤ 2*10⁹

• Pentru 20 puncte, 1 ≤ N ≤ 2000

• Pentru alte 30 puncte, 1 ≤ N ≤ 400000

Exemplu

Cum se trimit solutii?