409182: GYM103451 B Sum of sums
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
B. Sum of sumstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
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$$$.
InputIn 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$$$.
OutputOutput answer modulo $$$10^9+7$$$.
ExamplesInput5 0 1 2 3 4 5Output
15Input
5 1 1 2 3 4 5Output
105Input
3 2 1 2 3Output
42