После великог успеха игре JAG™, компанија “Најбољи лтд.” је направила још бољи наставак, BUG™.

У овој учествује \(10^9 + 7\) играча и победник се одлучује случајним избором. Да би избор био случајан, компанија је поставила строга правила за бирање тог играча. Прво нумеришу играче са идентификационим бројевима од \(0\) до \(10^9+6\). Затим изаберу низ \(A\) са \(N\) елемената и број \(k\). Потом дефинишу победника као играча који има идентификациони број \(f(A,k) \mod (10^9 + 7)\), где је:

• \(f(T,k) = \sum_{i=1}^{i \leq len(T)} T_i\), за \(k=0\), где је \(len(T)\) дужина низа \(T\).
• \(f(T,k) = \sum_{i=1}^{i \leq len(T)} \sum_{j=i}^{j\leq len(T)} f(T[i...j],k-1)\) за \(k>0\), где је \(len(T)\) дужина низа \(T\) и \(T[i...j]\) подниз низа \(T\) са елементима од \(i\)-те до \(j\)-те позиције, тј. низ са елементима \(T_i, T_{i+1}, ..., T_{j-1}, T_{j}\).

Помозите компанији “Најбољи лтд.” и одредите победника игре.

Опис улаза

У првом реду налазе се бројеви \(N\), дужина низа \(A\) и \(k\). У наредном реду налази се \(N\) бројева, елементи низа \(A\).

Опис излаза

У једином реду стандардног излаза исписати једну вредност, победника игре, тј. вредност \(f(A,k) \mod (10^9 + 7)\).

Ограничења

• \(1 \leq N \leq 2 \cdot 10^{5}\).
• \(0 \leq k \leq 2 \cdot 10^{5}\).
• \(0 \leq A_i \leq 10^9\).

Тест примери су подељени у пет дисјунктних група:

• У тест примерима вредним 10 поена: \(N \leq 10^3\), \(k=1\).
• У тест примерима вредним 15 поена: \(N \leq 5\), \(k \leq 5\).
• У тест примерима вредним 25 поена: \(N \leq 300\), \(k \leq 300\).
• У тест примерима вредним 40 поена: \(N \leq 2000\), \(k \leq 2000\).
• У тест примерима вредним 10 поена: Нема додатних ограничења.

Примери

Пример 1

Улаз

5 0
1 6 3 4 7

Излаз

21

Објашњење

\(f(A,k) = f([1,6,3,4,7],0) = 1 + 6 + 3 + 4 + 7 = 21\), па је \(f(A,k) \mod (10^9 + 7) = 21\)

Пример 2

Улаз

5 1
1 6 3 4 7

Излаз

147

Објашњење

\(f(A,k) = f([1,6,3,4,7],1) = f([1],0) + f([1,6],0) + f([1,6,3],0) + f([1,6,3,4],0) + f([1,6,3,4,7],0) + f([6],0) + f([6,3],0) + f([6,3,4],0) + f([6,3,4,7],0) + f([3],0) + f([3,4],0) + f([3,4,7],0) + f([4],0) + f([4,7],0) + f([7],0) = 1 + 1 + 6 + 1 + 6 + 3 + 1 + 6 + 3 + 4 + 1 + 6 + 3 + 4 + 7 + 6 + 6 + 3 + 6 + 3 + 4 + 6 + 3 + 4 + 7 + 3 + 3 + 4 + 3 + 4 + 7 + 4 + 4 + 7 + 7 = 147\), па је \(f(A,k) \mod (10^9 + 7) =147\)