Funktion

Cerință

Se dă un șir $A$ de $N$ termeni pe care definim următoarea funcție $f(st,dr,k)$:

$f(st,dr,0) = v_{st} + v_{st+1} + ... + v_{dr}$
$f(st,dr,k) = \sum_{i=st}^{dr} \sum_{j=i}^{dr} f(i,j,k-1), k>0$

Practic funcția pe nivelul $0$ reprezintă suma unei subsecvențe, iar pe orice alt nivel facem suma valorilor funcției tuturor subsecvențelor de pe nivelul anterior.

Cât este $f(1,N,K)$ modulo $10^9+7$, pentru un $K$ dat?

Date de intrare

Pe prima linie se găsesc două numere întregi, $N$ și $K$.
Pe următorul rând se găsesc termenii șirului $A$.

Date de ieșire

Se va tipări valoarea dorită modulo $10^9+7$.

Restricții și precizări

• $1 \leq N, K \leq 10^6$;
• $-10^9 \leq A_i \leq 10^9$;

Subtaskuri

• Pentru $5p$ : $K=1$
• Pentru alte $15p$ : $N=2$
• Pentru alte $20p$ : $1 \leq N, K \leq 20$
• Pentru alte $15p$ : $A$ are un singur element nenul

Exemplul 1

stdin

3 1
1 2 3

stdout

20

Explicație

Problema cere practic suma tuturor subsecvențelor.

Exemplul 2

stdin

3 2
1 2 3

stdout

42