== include(page="template/taskheader" task_id="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{~0~} * 23^N-1^ + X{~1~} * 23^N-2^ + ... + X{~N-1~}$ modulo $10^9^ + 7$, unde $X{~i~}$ reprezintă efortul minim total pentru a strivi primii $i + 1$ gândaci.

Sunt $N$ gandaci in linie (atentie, nu cerc). Gandacul i are o carapace de rezistenta R[i].
Ai o manusa pe care o poti folosi pentru a lovi $K$ gandaci consecutivi deodata, la orice pozitie vrei, de cate ori vrei.
Atunci cand depui efortul $E$, toti gandacii cu rezistenta mai mica de $E$ sunt striviti, iar ceilalti nu patesc NIMIC. Efortul poate fi diferit de la o lovitura la alta. Se dau $T$ astfel de scenarii. Pentru fiecare scenariu, care e efortul total minim pentru a strivi toti gandacii?

h2. Date de intrare

Fişierul de intrare $peru.in$ contine pe prima linie numerele $N$ şi $K$, iar pe a doua linie un şir de $N$ numere.

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

h2. Date de ieşire

În fişierul de ieşire $peru.out$ conţine un singur număr reprezentând rezultatul obţinut.

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

h2. Restricţii

* $1 ≤ N ≤ 2500000$
 
* $1 ≤ K ≤ N$
 
* $1 ≤ S{~i~} ≤ 2 * 10^9^$
 
* Pentru $20$ puncte, $1 ≤ N ≤ 2000$
 
* Pentru alte $30$ puncte, $1 ≤ N ≤ 400000$
 
* Se recomanda parsarea fisierului de intrare

* $1 ≤ T, suma N-urilor, K ≤ 10^6^$
* Pentru $20%$ din punctaj $1 ≤ suma N-urilor ≤ 5000$
* Pentru $40%$ din punctaj $1 ≤ suma N-urilor ≤ 10^5^$
* Parsati intrarea
 
O(N) 100p
O(Nlog) 60p
O(NK) 20p

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

| 8 3
  3 2 9 8 7 11 3 4
| 720026253
|

| 3
7
1 1 2 3 2 1 1
5
2 3 2 3 2
5
1 3 1 3 1
| 5
6
5
|
 
h3. Explicaţie
 
...

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