← 返回题目列表

Codeforces · 1037/F

F. 最大减少

中文机器翻译题面 查看原题

给定一个由 $$$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$$$。