幽谷传响II

题目描述

Orange进入了一片连绵的山脉，这片山脉由 $n$ 座山峰组成，第 $i$ 座山峰的海拔为 $a_i$。

Orange定义一处幽谷：对于一片 连续且长度不超过 $k$ 的山脉 $[a_i, a_{i + 1} ... a_{i + k’}]$，其幽谷为其中海拔最低的山峰。

现在，Orange想求出这片山脉中所有的幽谷的海拔之和，请你帮助他完成这件事。由于答案可能很大，请你输出答案对 $10^9+7$ 取 $\bmod$ 的值。

形式化的说，你应该求出如下函数的值：

$$F = \sum_{i = 1}^n \sum_{j = i}^{ min(i+k-1,n)} \min_{p = i} ^ j a_p \pmod{10^9+7}$$

输入格式

输入共 2 行： 第一行为两个整数 $n,k$，表示山峰的数量和长度的限制。 第二行为 $n$ 个整数 $a_i$，表示各个山峰的海拔。

数据范围

$1 \le k \le n \le 10^6$ $1 \le a_i \le 10^6$

输出格式

输入一个整数，表示答案。

样例 #1

样例输入 #1

3 2
1 2 3

样例输出 #1

9

提示

样例解释1

对于 $[1，2，3]$，其存在长度为1的山脉$[1]，[2]，[3]$，其幽谷分别为他们自身，其存在长度为2的山脉$[1，2]，[2，3]$，其幽谷为1和2，因此所有合法幽谷之和为9。