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

Задача H. Тима и сумма степеней

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

1 секунда

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

256 мегабайт

У Тимы есть целое число $N$ и массив $A$ из $N$ целых чисел. Также у него есть два целых числа $M$ и $K$. Для каждого $i$ от $1$ до $N$-$M$+$1$ Тима хочет посчитать значение выражения $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

Замечание

Пояснение к примеру 1: При $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 )