题目描述

给定一个具有 $n$ 个顶点的环，顶点按顺时针从 $1$ 至 $n$ 标号，每个顶点的权值为 $a_i$。 规定每次跳跃步长为 $k$，总跳跃次数为 $m$。

跳跃规则如下：

1. 初始位置：从第 $1$ 个点出发（此为第 $1$ 次跳跃的起点）。
2. 跳跃逻辑：若当前处于第 $i$ 个点，则下一次会跳到第 $(i + k - 1) \bmod n + 1$ 个点。

求这 $m$ 次跳跃中，所有起点的权值之和，把答案对 $10^9 + 7$ 取模。

输入格式

第一行包含三个整数 $n, m, k$，分别表示顶点数量、总跳跃次数和跳跃步长。

第二行包含 $n$ 个整数，依次表示编号为 $1$ 至 $n$ 的顶点的权值 $a_1, a_2, \dots, a_n$。

输出格式

输出一个整数，表示 $m$ 次跳跃起点权值之和对 $10^9 + 7$ 取模后的值。

输入输出样例

5 3 2
1 2 3 4 5

9

说明/提示

样例解释

• 第 $1$ 次跳跃：起点为 $1$，权值为 $a_1 = 1$，跳到 $(1 + 2 - 1) \bmod 5 + 1 = 3$。
• 第 $2$ 次跳跃：起点为 $3$，权值为 $a_3 = 3$，跳到 $(3 + 2 - 1) \bmod 5 + 1 = 5$。
• 第 $3$ 次跳跃：起点为 $5$，权值为 $a_5 = 5$。
• 总权值和为 $1 + 3 + 5 = 9$。

数据范围

• 对于 $30\%$ 的数据：$1 \le n, m \le 10^3$
• 对于 $100\%$ 的数据：
  • $1 \le n \le 10^6$
  • $1 \le m \le 10^{18}$
  • $1 \le k \le n$
  • $0 \le a_i \le 10^9$
• 结果需对 $10^9 + 7$ 取模。