CF1037F Maximum Reduction

给定一个长为 $n$ 的数组 $a$ 和一个数 $k$（$2\le k\le n$），数组从 $1$ 开始编号。 请阅读下列程序伪代码，并输出 $z(a,k)$ 对 $10^9+7$ 取模后的值。 **z 函数的大意：** - 在数组 $a$ 中，记录下从左到右每一段长度为 $k$ 的区间内的最大值。 - 返回的是这些最大值之和，加上这些最大值从左到右排列形成的新的数组 $b$ 的 $z(b,k)$ 的值，即这是个递归函数。 - 如果数组长度比 $k$ 小，返回 $0$。

第一行输入 $n$ 和 $k$（$2\le k\le n\le 10^6$）。 第二行输入 $n$ 个数 $a_1,a_2,\cdots,a_n$（$1\le a_i\le 10^9$）。

输出 $z(a,k)$ 对 $10^9+7$ 取模后的值。

In the first example: - for $ a=(9,1,10) $ , $ ans=19 $ and $ b=(9,10) $ , - for $ a=(9,10) $ , $ ans=10 $ and $ b=(10) $ , - for $ a=(10) $ , $ ans=0 $ . So the returned value is $ 19+10+0=29 $ . In the second example: - for $ a=(5,8,7,1,9) $ , $ ans=25 $ and $ b=(8,8,9) $ , - for $ a=(8,8,9) $ , $ ans=9 $ and $ b=(9) $ , - for $ a=(9) $ , $ ans=0 $ . So the returned value is $ 25+9+0=34 $ .