Iterated Subsegment Sum Expansion

Given an array \(a_1,a_2,\dots,a_n\) and an integer \(k\), consider the following recursively defined function:

For any interval \([l, r]\), define the \(k\)th order subsegment sum \(sum_{k,l,r}\) as

[ sum_{k,l,r}=\begin{cases} \sum\limits_{i=l}^{r}a_i, & k=1\[8pt] \sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}sum_{k-1,i,j}, & k\ge 2 \end{cases} ]

Alice stands initially at position \(1\) on a line of cells. Every time he expands his territory by one cell to the right (i.e. increasing the right boundary from \(r\) to \(r+1\)), he must correctly compute \(sum_{k,1,r}\) for the current segment \([1, r]\). Your task is to help him by computing the final answer \(sum_{k,1,n}\) given the array \(a\) and the integer \(k\).

A combinatorial analysis shows that the answer can be written in closed‐form as:

[ sum_{k,1,n}= \sum_{t=1}^{n} a_t; \binom{t+k-2}{k-1} ; \binom{n-t+k-1}{k-1} ]

Since the answer can be extremely large, output it modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \le n \le 10^5\), \(1 \le k \le 10^5\)).

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).

outputFormat

Output a single integer, the value of \(sum_{k,1,n}\) modulo \(10^9+7\).

sample

3 1
1 2 3

6