B. Sum of sums
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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 \gt 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$$$.

Input

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

Output answer modulo $$$10^9+7$$$.

Examples
Input
5 0
1 2 3 4 5
Output
15
Input
5 1
1 2 3 4 5
Output
105
Input
3 2
1 2 3
Output
42