← 返回题目列表

AtCoder · awc0037_c

C. 连续区间的乘积之和

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

分数: 366 分

问题陈述

高桥有一系列 N 正整数。的 i- 第一个元素 序列的 (1 \leq i \leq N) 是 A_i.

高桥想要考虑所有 间隔组成 K 连续元素 该序列,并计算每个区间中元素的乘积。

有 N - K + 1 间隔组成 K 连续元素。对于每个 i = 1, 2, \ldots, N - K + 1,我们可以取由以下组成的区间 K 元素来自 i-第 (i + K - 1)- 第一个元素。

计算的乘积 K 每个区间中的元素, A_i \times A_{i+1} \times \cdots \times A_{i+K-1},求所有区间的乘积之和,即

\sum_{i=1}^{N-K+1} \prod_{j=i}^{i+K-1} A_j

由于答案可能非常大,因此输出除以的余数 10^9 + 7.

约束

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 所有输入均为整数

输入

N K
A_1 A_2 \ldots A_N
  • 第一行包含一个整数 N 表示序列的长度和一个整数 K 表示间隔的长度,以空格分隔。
  • 第二行包含 N 正整数 A_1, A_2, \ldots, A_N 表示序列的元素,以空格分隔。

输出

在一行中输出所有区间的乘积之和时的余数 K 连续元素除以 10^9 + 7.


示例输入 1

5 2
1 2 3 4 5

示例输出 1

40

示例输入 2

6 3
2 3 1 4 2 5

示例输出 2

66

示例输入 3

10 4
100 200 300 400 500 600 700 800 900 1000

示例输出 3

799992244