409182: GYM103451 B Sum of sums

Let's define function $$$f$$$ from array of non-negative numbers $$$A$$$ of $$$n$$$ elements in the following way: $$$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 > 0$$$, where $$$A[l, r]$$$ - subarray of array $$$A$$$ with indexes from $$$l$$$ to $$$r$$$. You are given $$$n$$$, $$$k$$$ and array $$$A$$$ of $$$n$$$ elements. Compute $$$f(A, k)$$$ modulo $$$10^9+7$$$.

In first line you are given two numbers: $$$1 \le n \le 2 * 10^5$$$ and $$$0 \le k \le 2 * 10^5$$$. In the second line you are given array of $$$n$$$ integers $$$0 \le a_i \le 10^9$$$.

Output answer modulo $$$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