페루

오늘 아침 로키가 책상 위에서 딱정벌레 $N$마리를 발견했다. 딱정벌레는 0번부터 $N-1$번까지 번호가 매겨져 있고, 각 딱정벌레 $i$의 세기는 $S_i$이다. 로키는 수학 숙제를 하려고 딱정벌레를 으깨고 싶어 한다. 이를 위해 특별한 장갑을 샀고, 이 장갑으로 연속된 딱정벌레 $K$마리를 한 번에 칠 수 있다. 로키가 노력 $E$를 들이면 세기가 $E$ 이하인 딱정벌레는 으깨지고, 나머지는 다치지 않고 남는다. 으깨진 딱정벌레도 책상 위의 위치는 그대로 유지된다. 장갑은 원하는 만큼 몇 번이든 사용할 수 있다.

로키는 각 $1 \le i \le N$에 대해 처음 $i$마리의 딱정벌레를 으깨는 데 필요한 최소 총 노력을 구할 수 있는지 알고 싶어 한다. 수가 너무 많으므로, 다음 식을 $10^9 + 7$로 나눈 나머지를 출력한다. $X_0 \times 23^{N-1} + X_1 \times 23^{N-2} + \cdots + X_{N-1}$. 여기서 $X_i$는 처음 $i+1$마리의 딱정벌레를 으깨는 데 필요한 최소 총 노력이다.

• $1 \le N \le 2\,500\,000$
• $1 \le K \le N$
• $1 \le S_i \le 2\,000\,000\,000$