题目内容

在一条直线上规划 $5$G 组网时，需要依次在若干点位部署基站。每个点位 $p$ 对应一个已知场强 $a[p]$。为了评估信号干扰情况，需要计算每一座基站被左右邻近基站干扰的程度。

对位置 $p$ 的基站，定义两个观察区间。左侧观察区间从 $p-1$ 开始向左延伸，最多包含 $t$ 个基站；右侧观察区间从 $p+1$ 开始向右延伸，最多包含 $t$ 个基站。所有观察都必须限制在数组边界内。

在左侧观察区间中，沿着从近到远的方向寻找第一个场强严格大于 $a[p]$ 的基站。如果找到，设其下标为 $L$，则左侧干扰指数为 $a[p]\times(p-L)$；如果不存在这样的基站，则左侧干扰指数为 $0$。类似地，在右侧观察区间中寻找第一个场强严格大于 $a[p]$ 的基站。如果找到，设其下标为 $R$，则右侧干扰指数为 $a[p]\times(R-p)$；如果不存在，则右侧干扰指数为 $0$。

每座基站的总干扰指数定义为左侧干扰指数与右侧干扰指数之和。请计算所有基站的总干扰指数之和，并对 $10^9+7$ 取模后输出。

约束条件：

• 数组 $a$ 的长度 $m$ 满足 $1 \le m \le 10^5$。
• 每个场强 $a[p]$ 满足 $1 \le a[p] \le 10^9$。
• $t$ 满足 $1 \le t \le m$。

输入描述

第一行包含若干个以空格分隔的整数，依次表示数组 $a$ 中从左到右每个点位上的基站场强。

第二行包含一个整数 $t$，表示向一侧最多观察的基站座数。

输出描述

输出一个整数，表示所有基站的总干扰指数之和对 $10^9+7$ 取模后的结果。

样例1

输入

3 1 4 1 5
2

输出

18

说明

下标从 0 开始。

下标 0 场强为 3。左侧无基站，干扰为 0。右侧观察区间最多包含 2 个基站，场强分别为 1、4；第一个严格大于 3 的是场强 4，距离为 2，右侧干扰为 $3 \times 2 = 6$，总干扰为 6。

下标 1 场强为 1。左侧第一个严格大于 1 的是场强 3，距离为 1，贡献 $1 \times 1 = 1$；右侧第一个严格大于 1 的是场强 4，距离为 1，贡献 $1 \times 1 = 1$，总干扰为 2。

下标 2 场强为 4。左侧场强 1 和 3 都不大于 4，左侧干扰为 0；右侧场强 1 和 5 中第一个严格大于 4 的是场强 5，距离为 2，右侧干扰为 $4 \times 2 = 8$，总干扰为 8。

下标 3 场强为 1。左侧第一个严格大于 1 的是场强 4，距离为 1，贡献 $1 \times 1 = 1$；右侧第一个严格大于 1 的是场强 5，距离为 1，贡献 $1 \times 1 = 1$，总干扰为 2。

下标 4 场强为 5。左侧场强 1 和 4 都不大于 5，右侧无基站，总干扰为 0。

求和得到 $6+2+8+2+0=18$，取模后仍为 18。

样例2

输入

10 20 15 30
1

输出

40

说明

下标从 0 开始。

下标 0 场强为 10。左侧无基站，干扰为 0。右侧观察区间只包含下标 1，场强 20 严格大于 10，距离为 1，右侧干扰为 $10 \times 1 = 10$，总干扰为 10。

下标 1 场强为 20。左侧下标 0 场强 10 不大于 20，左侧干扰为 0；右侧观察区间只包含下标 2，场强 15 不大于 20，右侧干扰为 0。虽然更右侧下标 3 的场强 30 大于 20，但距离为 2，超出了 $t=1$ 的观察范围，因此不计入干扰。总干扰为 0。

下标 2 场强为 15。左侧观察区间只包含下标 1，场强 20 严格大于 15，距离为 1，左侧干扰为 $15 \times 1 = 15$；右侧观察区间只包含下标 3，场强 30 严格大于 15，距离为 1，右侧干扰为 $15 \times 1 = 15$，总干扰为 30。

下标 3 场强为 30。左侧观察区间只包含下标 2，场强 15 不大于 30，右侧无基站，总干扰为 0。

求和得到 $10+0+30+0=40$，取模后仍为 40。

样例3

输入

1000000000 500000000 1 1000000000
3

输出

499999995

说明

下标从 0 开始。

下标 0 场强为 1000000000。左侧无基站，右侧观察区间内场强依次为 500000000、1、1000000000，没有严格大于 1000000000 的值，因此总干扰为 0。

下标 1 场强为 500000000。左侧第一个严格大于它的是下标 0，距离为 1，贡献 $500000000 \times 1 = 500000000$；右侧第一个严格大于它的是下标 3，距离为 2，贡献 $500000000 \times 2 = 1000000000$，总干扰为 1500000000。

下标 2 场强为 1。左侧第一个严格大于它的是下标 1，距离为 1，贡献 $1 \times 1 = 1$；右侧第一个严格大于它的是下标 3，距离为 1，贡献 $1 \times 1 = 1$，总干扰为 2。

下标 3 场强为 1000000000。左侧观察区间内场强依次为 1、500000000、1000000000，没有严格更大的值；右侧无基站，因此总干扰为 0。

总和为 $1500000000+2=1500000002$。对 $10^9+7$ 取模，$1500000002-1000000007=499999995$，因此输出 499999995。

样例4

输入

7
1

输出

0

说明

只有一个下标 0 的基站，场强为 7。它的左右观察区间都为空，因此左侧和右侧干扰指数均为 0，总和为 0。