题目描述

给出一个长度为n 的环，一个常数 k ，每次跳跃会从第 i 个点跳到第 ( i + k ) m o d n + 1 个点（从第一个点开始跳）。每一个点都有一个权值，记为 ai。每次询问给出一个 m，求 m 次跳跃的权值和对 1e9+7取模。

输入格式

第一行输入整数n、k 第二行输出n个整数，代表每个点的权值 第三行输出一个整数m，代表跳跃次数

注：起跳点是1号。

输出格式

输出一个整数，代表答案

输入样例

6 10
1 2 3 4 5 6
3

输出样例

12

数据规模

1<= n<=10^6，1<=m<=10^18，1<=k<=n，0<=ai<=10^9