注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "peru.h"。

题目描述

题目译自 Romanian Master of Informatics 2020 Day1 T3 「Peru」

今天早上，Roxy 在她的书桌上发现了 $N$ 只甲虫。这些甲虫从 $0$ 到 $N-1$ 编号，每只甲虫 $i$ 都有一个力量值 $S_{i}$。Roxy 想把这些甲虫消灭掉，好专心做她的数学作业。为此，她买了一只特别的手套，可以用来拍击连续的 $K$ 只甲虫。只要 Roxy 使出的力气 $E$ 达到一定值，那些力量 $S_{i}$ 小于等于 $E$ 的甲虫就会被压扁，而其他甲虫则毫发无伤。被压扁的甲虫依然留在原位，Roxy 可以随意多次使用这只手套。

Roxy 想知道，你能不能对于每个 $1 \leq i \leq N$ 帮她算出压扁前 $i$ 只甲虫所需的最小总力气。因为数字太多，她同意你只需要给她一个最终结果：$X_{0} \cdot 23^{N-1} + X_{1} \cdot 23^{N-2} + \ldots + X_{N-1}$ 对 $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$ 只甲虫的力量。

8 3
3 2 9 8 7 11 3 4

720026253

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

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 2.5\cdot 10^6$
• $1 \leq K \leq N$
• $1 \leq S_{i} \leq 2\cdot 10^9$

详细子任务附加限制及分值如下表所示。