U205695 前缀和 Additional Deliciousness

疫情好转后，ckj 来到了北京，终于与 jyn 相见了，他们俩坐在烛光下，享受着丰盛的晚餐。

晚餐共有 $n$ 道菜，第 $i$ 道有美味值 $a_i$。ckj 和 jyn 在讨论这一顿饭的总美味值。ckj 认为，前一道菜对于后面每道菜的美味值是有影响的。这一道菜的实际美味值因人而异，对于有的人来说，美味值是所有菜的美味值的前缀和之和，然而对于有的人来说，前一道菜对后面菜的影响会更大一点，美味值是所有菜的美味值的前缀和的前缀和之和。形象地说，若一个人的品味值为 $k$，那么他认为这 $n$ 道菜的“总美味值”是对 $a$ 做 $k$ 次前缀和产生的新序列的元素之和。 现在 ckj 想知道，当给定 $n,k$ 和 $a$ 序列后，总美味值是多少？答案对 $10^9+7$ 取模。

本题由于 $n$ 过大，所以我们使用[这段代码](https://www.luogu.com.cn/paste/7ulkasfv)来读入。 共一行，第一行有 $3$ 个整数 $n,k,S$，意义见题目描述和上面的那段代码。

一行一个整数表示答案对 $10^9+7$ 取模后的值。

**【样例 1 解释】** $a$ 序列是 $\{18,103,528\}$。 $a$ 的一次前缀和是 $\{18,121,649\}$。和为 $788$。故美味值就是 $788$，对 $10^9+7$ 取模后是 $788$。 **【数据范围】** **本题采取捆绑测试。** | 子任务编号 | 分值 | 特殊性质 | | :-: | :-: | :-: | | $1$ | $10$ | $n,k \le 10^3$ | | $2$ | $30$ | $n \le 10^5, k \le 10^4$ | | $3$ | $60$ | 无特殊性质 | 对于 $100\%$ 的数据，$1 \le n \le 10^7$，$1 \le S,k \le 10^9$。