题目背景

译自 8th Romanian Master of Informatics, RMI 2020 D1T3。$\texttt{0.2s,0.25G}$。

题目描述

这是一道（函数式）交互题。

有 $N$ 只甲虫在桌面上排成一行，从左到右编号为 $0\sim N-1$。第 $i$ 只甲虫的体力为 $S_i$。

每次可以选择连续的至多 $K$ 只甲虫，用 $E$ 的力量去击打它们。被击打的甲虫，若体力不大于 $E$，则会死亡，否则无事发生。死亡的甲虫会留在原地，可以击打死亡的甲虫。

可以多次击打甲虫，每次 $E$ 的大小可以不同。

定义 $f(i)$ 为：杀死最左边的 $i$ 只甲虫，需要力量和的最小值。对于 $i=1,2,\cdots,N$，求出 $f(i)$。

为了减小输出量，你只需要求出 $\displaystyle \left(\sum_{1\le i\le N} f(i)\cdot 23^{N-i}\right)\bmod (10^9+7)$。

实现细节

你不需要，也不应该实现 main 函数。

你需要实现以下的函数：

int solve(int N, int K, int S[]);

交互库会调用 solve 函数恰好一次。参数的含义：

• N：甲虫数量。
• K：一次击打最多击打的连续甲虫数。
• S：每只甲虫的体力。

返回一个整数表示 $\displaystyle \left(\sum_{1\le i\le N} f(i)\cdot 23^{N-i}\right)\bmod (10^9+7)$。

输入格式

Sample grader 按照如下格式读取输入：

第一行，两个正整数 $N,K$；

第二行，$N$ 个正整数 $S_1,S_2,\cdots,S_{N}$。

输出格式

Sample grader 输出一个整数，表示选手返回的答案。

8 3
3 2 9 8 7 11 3 4

720026253

提示

样例解释

$f$ 的值分别为 $3,3,9,12,12,20,23,23$。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le K\le N\le 2.5\times 10^6$；
• $1\le S_i\le 2\times 10^9$。

子任务编号	$N,Q\le$	得分
$1$	$2\times 10^3$	$18$
$2$	$4\times 10^5$	$31$
$3$	$2.5\times 10^6$	$51$