Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

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

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

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

Опис улаза

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

Опис излаза

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

Ограничења

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

Примери

Пример 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\)