Определим функцию $$$f$$$ от массива целых неотрицательных чисел $$$A$$$ из $$$n$$$ элементов следующим образом: $$$f(A, 0) = $$$ $$$\sum\limits_{i=1}^n a_i$$$;
$$$f(A, i) = $$$$$$\sum\limits_{l=1}^n \sum\limits_{r=l}^n$$$ $$$f(A[l, r], i - 1)$$$, $$$i \gt 0$$$, где $$$A[l, r]$$$ - подмассив массива $$$A$$$ с индексами элементов от $$$l$$$ до $$$r$$$. Вам даны числа $$$n$$$, $$$k$$$ и массив $$$A$$$ из $$$n$$$ элементов. Вычислите $$$f(A, k)$$$ по модулю $$$10^9+7$$$.
В первой строке входных данных находится два целых числа: $$$1 \le n \le 2 * 10^5$$$ и $$$0 \le k \le 2 * 10^5$$$. Во второй строке содержится массив из $$$n$$$ целых чисел $$$0 \le a_i \le 10^9$$$.
Выведите единственное число - ответ на задачу по модулю $$$10^9+7$$$.
5 0 1 2 3 4 5
15
5 1 1 2 3 4 5
105
3 2 1 2 3
42
$$$10^9 + 7$$$ – простое число.
| Krosh Kaliningrad Contest 2 |
|---|
| Закончено |
