Республиканская олимпиада по информатике 2017 год, Павлодар

(Тима және дәрежелер қосындысы)

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Тимада $N$ бүтін саны және $N$ саннан тұратын $A$ массивы бар. Тағыда ода $M$ және $K$ бүтін сандары бар. Барлық $1$—ден $N$-$M$+$1$—ге дейінгі $i$ бүтін саны үшін Тима мынадай өрнектің $1^K \cdot A_{i} + 2^K \cdot A_{i + 1} + \cdots + M^K \cdot A_{i + M - 1}$ мәнің санағысы келеді. Оған осы есепті шығаруға көмектесіңіз.

Формат входного файла

Бірінші жолда үш бүтін сан берілген $N$($1 \le N \le 10^5$),$M$($1 \le M \le N$) және $K$($0 \le K \le 20$). Екінші жолда $N$ бүтін сан берілген $A_1,A_2, \cdots, A_N$ ($1 \le A_i \le 10^9$).

Формат выходного файла

$N$-$M$+$1$ жол шығарыңыз, $i$-ші жолда $1^K \cdot A_{i} + 2^K \cdot A_{i + 1} + \cdots + M^K \cdot A_{i + M - 1}$ өрнегінің мәнің $10^9 + 7$ бөлгендегі қалдығын шығарыңыз.

Система оценки

Есеп бес бөлімнен тұрады:

1. $1 \le N \le 100, 0 \le K \le 3,1 \le A_i \le 10$. Бөлім $7$ ұпайға бағаланады.
2. $1 \le N \le 10^4, 0 \le K \le 20,1 \le A_i \le 10^9$. Бөлім $12$ ұпайға бағаланады..
3. $1 \le N \le 10^5, 0 \le K \le 1,1 \le A_i \le 10^9$. Бөлім $13$ ұпайға бағаланады.
4. $1 \le N \le 10^5, K = 2,1 \le A_i \le 10^9$. Бөлім $20$ ұпайға бағаланады.
5. $1 \le N \le 10^5, 0 \le K \le 20,1 \le A_i \le 10^9$. Бөлім $48$ ұпайға бағаланады.

Примеры:

Вход

5 3 2
1 2 3 4 5

Ответ

36
50
64

Вход

3 2 0
7 3 2

Ответ

10
5

Замечание

Бірінші мысалға түсіндірме: $i = 1$ болғанда, $1^K \cdot A_1 + 2^K \cdot A_2 + 3^K \cdot A_3$ = $1^2 \cdot 1 + 2^2 \cdot 2 + 3^2 \cdot 3 = 1 + 8 + 27 = 36$. $i = 2$ болғанда, $1^K \cdot A_2 + 2^K \cdot A_3 + 3^K \cdot A_4$ = $1^2 \cdot 2 + 2^2 \cdot 3 + 3^2 \cdot 4 = 50$. $i = 3$ болғанда, $1^K \cdot A_3 + 2^K \cdot A_4 + 3^K \cdot A_5$ = $1^2 \cdot 3 + 2^2 \cdot 4 + 3^2 \cdot 5 = 64$. ( Temirlan Satylkhanov )