分数: 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