给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$ 和一个整数 $$$k$$$ ($$$2 \le k \le n$$$),其中数组的每个元素由 $$$a_i$$$ 表示 ($$$0 \le i < n$$$)。对 $$$a$$$ 执行下面给出的操作 $$$z$$$ 并打印 $$$z(a,k)$$$ 模 $$$10^{9}+7$$$ 的值。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le k \le n \le 10^6$$$) - 初始数组 $$$a$$$ 和参数 $$$k$$$ 的长度。
输入的第二行包含 $$$n$$$ 整数 $$$a_0, a_1, \ldots, a_{n - 1}$$$ ($$$1 \le a_{i} \le 10^9$$$) — 数组 $$$a$$$ 的元素。
输出
输出唯一的整数,即 $$$z(a,k)$$$ 模 $$$10^9+7$$$ 的值。
示例
输入 #1
3 2 9 1 10
输出 #1
29
输入 #2
5 3 5 8 7 1 9
输出 #2
34
注意
在第一个示例中:
- 对于 $$$a=(9,1,10)$$$、$$$ans=19$$$ 和 $$$b=(9,10)$$$,
- 对于 $$$a=(9,10)$$$、$$$ans=10$$$ 和 $$$b=(10)$$$,
- 对于 $$$a=(10)$$$,$$$ans=0$$$。
所以返回值为$$$19+10+0=29$$$。
在第二个示例中:
- 对于 $$$a=(5,8,7,1,9)$$$、$$$ans=25$$$ 和 $$$b=(8,8,9)$$$,
- 对于 $$$a=(8,8,9)$$$、$$$ans=9$$$ 和 $$$b=(9)$$$,
- 对于$$$a=(9)$$$,$$$ans=0$$$。
所以返回值为$$$25+9+0=34$$$。