kmedie

Cerință

Definim KMedia unui șir de numere naturale ca fiind media aritmetică a tuturor elementelor șirului după ce am eliminat cele mai mari $k$ numere și cele mai mici $k$ numere.
De exemplu: pentru șirul $1 \ 7 \ 4 \ 2 \ 5 \ 9$ și $k = 2$, KMedia șirului este $(4 + 5)/ 2 = 9/2 = 4$, unde $/$ este câtul operației de împărțire pe numere naturale.

Se dau trei numere naturale $n$, $m$, $k$ și un șir de $n$ numere întregi pentru care dorim să calculăm suma KMediilor tuturor subsecvențelor de lungime $m$ modulo $1 \ 000 \ 000 \ 007$.

Date de intrare

Pe prima linie a fișierului kmedie.in se află cele trei numere naturale $n$, $m$ și $k$. Pe următoarea linie se află $n$ numere naturale reprezentând elementele șirului.

Date de ieșire

În fișierul kmedie.out se va scrie un singur număr reprezentand suma tuturor KMediilor subsecvențelor de lungime $m$ ale șirului, modulo $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $1 \leq k,n,m \leq 300 \ 000$;
• $2 \times k \lt m \leq n$;
• Elementele șirului sunt numere naturale din intervalul $[1; 1 \ 000 \ 000]$;
• Pentru $31$ puncte avem $k, n, m \leq 1 \ 000$;
• Pentru alte $27$ de puncte avem $k = 1$;
• Pentru restul de $42$ de puncte nu sunt restricții suplimentare.

Exemplu

kmedie.in

10 6 2 
3 1 7 4 2 5 9 3 10 2

kmedie.out

19

Explicație

• Prima subsecvență este $3 \ 1 \ 7 \ 4 \ 2 \ 5$, a cărei KMedie este $(3+4)/2=7/2=3$;
• A doua subsecvență este $1 \ 7 \ 4 \ 2 \ 5 \ 9$, a cărei KMedie este $(4+5)/2=9/2=4$;
• A treia subsecvență este $7 \ 4 \ 2 \ 5 \ 9 \ 3$, a cărei KMedie este $(4+5)/2=9/2=4$;
• A patra subsecvență este $4 \ 2 \ 5 \ 9 \ 3 \ 10$, a cărei KMedie este $(4+5)/2=9/2=4$;
• A cincea subsecvență este $2 \ 5 \ 9 \ 3 \ 10 \ 2$, a cărei KMedie este $(5+3)/2=8/2=4$.

Suma tuturor KMediilor este $3+4+4+4+4 = 19$, care modulo $1 \ 000 \ 000 \ 007$ ramâne tot $19$, deoarece $19 \ \% \ 1 \ 000 \ 000 \ 007 = 19$.