今天早上，Roxy 在她的桌子上发现了 $N$ 只甲虫。这些甲虫编号为 $0$ 到 $N-1$，每只甲虫 $i$ 都有一个强度 $S_i$。Roxy 想要压碎这些甲虫以便完成她的数学作业。为此，她买了一只特殊的手套，可以用它来击打一段长度为 $K$ 的连续甲虫序列。如果 Roxy 使用的力度为 $E$，那么所有强度 $S_i$ 小于或等于 $E$ 的甲虫都会被压碎，而其他甲虫则保持完好。被压碎的甲虫会保持它们在桌子上的位置。Roxy 可以根据需要多次使用这只手套。

Roxy 想知道你是否能计算出压碎前 $i$ 只甲虫所需的最小总力度，对于每个 $1 \le i \le N$。由于数字太多，Roxy 同意你只需给出以下表达式的结果：$X_0 \cdot 23^{N-1} + X_1 \cdot 23^{N-2} + \dots + X_{N-1} \pmod{10^9 + 7}$，其中 $X_i$ 表示压碎前 $i+1$ 只甲虫所需的最小总力度。

实现细节

选手必须实现以下函数：

int solve(int N, int K, int* S);

该函数将被调用恰好一次，并必须返回上述表达式对 $10^9 + 7$ 取模后的结果。函数的参数为 $N$（甲虫数量）、$K$（手套可以击打的连续子序列长度）以及 $S$（一个长度为 $N$ 的数组，其中 $S_i$ 表示甲虫 $i$ 的强度）。

数据范围

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

子任务

• 子任务 1（18 分）：$1 \le N \le 2\,000$
• 子任务 2（31 分）：$1 \le N \le 400\,000$
• 子任务 3（51 分）：无额外限制。

样例

输入 1

8 3
3 2 9 8 7 11 3 4

输出 1

720026253

说明

数组 $X$ 为 $\{3, 3, 9, 12, 12, 20, 23, 23\}$。