题目描述

给出一个长度为 $n$ 的环和一个常数 $k$，每次会从第 $i$ 个点跳到第 $(i+k) \mod n+1$ (就是 $k+1$ 个点)个点总共跳了 $m$ 次。每一个点都有一个权值，记为 $a_i$，​求 $m$ 次跳跃的权值和对$10^9+7$ 取模。

输入

现在给你第一行：$n，k，q，$ 代表 $n$ 个数字，$k$ 步长，$q$ 个询问，第二行 $n$ 个 $a_i$ 代表权值。

接下来 $q$ 行，每行一个 $m$ 代表询问(每次都是从 $1$ 开始跳，第一步是进入环就是到 $1$ 这个位置)。

输出

对于每个 $m$ 输出他的权值和对 $10^9+7$ 取模的值。

样例

4 1 4
1 2 3 4
1 2 3 4

1 4 5 8

提示

$m=1,ans = 1, m=2,ans=1+3, m=3,ans=1+3+1, m=4,ans=1+3+1+3.$

数据范围

$1 \le n \le 10^5，1\le m \le10^{18}$，

$1 \le k \le n，0 \le a_i \le 10^9，q \le 10^5$。