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:

• \(f(T,k) = \sum_{i=1}^{i \leq len(T)} T_i\), ahol \(k=0\), a \(len(T)\) pedig a \(T\) sorozat hossza.
• \(f(T,k) = \sum_{i=1}^{i \leq len(T)} \sum_{j=i}^{j\leq len(T)} f(T[i...j],k-1)\) ahol \(k>0\), a \(len(T)\) a \(T\) sorozat hossza, a \(T[i...j]\) pedig a \(T\) sorozat része az \(i\)-edik elemtől a \(j\)-edik elemig, vagyis egy sorozat \(T_i, T_{i+1}, ..., T_{j-1}, T_{j}\) elemekkel.

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

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

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

• Tesztpéldák, melyek \(10\) pontot érnek: \(N \leq 10^3\), \(k=1\).
• Tesztpéldák, melyek \(15\) pontot érnek: \(N \leq 5\), \(k \leq 5\).
• Tesztpéldák, melyek \(25\) pontot érnek: \(N \leq 300\), \(k \leq 300\).
• Tesztpéldák, melyek \(40\) pontot érnek: \(N \leq 2000\), \(k \leq 2000\).
• Tesztpéldák, melyek \(10\) pontot érnek: nincs külön korlátozás.

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\)