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

A „Legjobbak ltd.” vállalat JAG™ nevű játékának sikerén felbuzdulva elkészítette annak folytatását, a még érdekesebb BUG™-ot.

Ebben a játékban \(10^9 + 7\) játékos vesz részt, a győztes kiválasztása véletlenszerűen történik. Hogy a döntés valóban véletlenszerűen történjen a vállalat szigorú feltételekhez kötötte az adott versenyző kiválasztását. Először is \(0\)-tól \(10^9+6\)-ig terjedő azonosító számokkal látják el a versenyzőket. Ezután kiválasztásra kerül az \(A\) sorozat \(N\) elemmel és a \(k\) szám. Ezután meghatározzák a győztest, azt a játékost, akinek identifikációs száma \(f(A,k) \mod (10^9 + 7)\), ahol:

Segítsetek a “Legjobbak ltd.” vállalatnak, és határozzátok meg a verseny győztesét!

Bemenet

Az első sorban az \(N\)(az \(A\) sorozat hossza) és a \(k\) számok állnak. A következő sorban \(N\) szám áll. Ezek az \(A\) sorozat elemei.

Kimenet

A szabványos kimenet egyetlen sorában kiíratni egyetlen értéket, a játék győztesét, vagyis az \(f(A,k) \mod (10^9 + 7)\) értéket!

Korlátozások

A tesztpéldák öt független csoportba oszthatók:

Példák

1. példa

Bemenet

5 0
1 6 3 4 7

Kimenet

21

Magyarázat

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

2. példa

Bemenet

5 1
1 6 3 4 7

Kimenet

147

Magyarázat

\(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\), tehát \(f(A,k) \mod (10^9 + 7) =147\)