Sommes Partielles

Cerință

Se dă un șir $A$ de $N$ elemente cu valori întregi.
Se va aplica următoarea operație șirului $A$ de $T$ ori:

Fie $S$ șirul de sume parțiale ale lui $A$, a.î $S_i$ = $A_1 + A_2 + ... + A_i$.
Șirul $A$ se inlocuiește cu șirul $S$

Care va fi suma elementelor din șirul $A$ după aplicarea tuturor operațiilor?
Suma va fi afișată modulo $10^9+7$.

Date de intrare

Pe prima linie se găsesc două numere întregi, $N$ și $T$.
Pe următoarea linie se găsesc valorile șirului $A$.

Date de ieșire

Suma elementelor din $A$ după aplicarea celor $T$ operații modulo $10^9+7$.

Restricții și precizări

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

Subtaskuri

• Pentru $15p$ : $N \cdot T \leq 10^6$
• Pentru alte $15p$ : $A$ are un singur element nenul
• Pentru alte $10p$ : Toate elementele din $A$ sunt $1$

Exemplul 1

stdin

4 3
1 2 -1 1

stdout

37

Explicație

Șirul $A$ are valorile după cum urmează
După $0$ operații $A=(1,2,-1,1)$
După $1$ operație $A=(1,3,2,3)$
După $2$ operații $A=(1,4,6,9)$
După $3$ operații $A=(1,5,11,20)$
Suma valorilor din $A$ după $3$ operații este $37$