【知识点】
倍增法（英语：binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。
这个方法在很多算法中均有应用，其中最常用的是 RMQ 问题和求 LCA（最近公共祖先）。
首先，我们来看一个问题：如何用尽可能少的砝码称量出 $[0,\ 31]$ 之间的所有重量？（只能在天平的一端放砝码）。
答案是使用 $1\ 2\ 4\ 8\ 16$ 这五个砝码，可以称量出 $[0,\ 31]$ 之间的所有重量。每次我们都选择 $2$ 的整次幂作砝码的重量，就可以使用极少的砝码个数量出任意我们所需要的重量。
为什么说是极少呢？因为如果我们要量出 $[0,\ 1023]$ 之间的所有重量，只需要 $9\ (2^{10}=1024)$ 个砝码，需要量出 $[0,\ 1048575]$ 之间的所有重量，只需要 $19\ (2^{20}=1048576)$ 个。如果我们的目标重量翻倍，砝码个数只需要增加 $1$。这叫“对数级”的增长速度，因为砝码的所需个数与目标重量的范围的对数成正比。


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

$n\ (1 \leq n \leq 10^6)$
$m\ (1 \leq m \leq 10^{18})$
$k\ (1 \leq k \leq n)$
$a_i\ (0 \leq a_i \leq 10^9)$

1