**时间限制：** 1 秒 


**空间限制：** 512 MB

**相关文件：** 题目目录




## 问题描述

小K最近刚刚习得了一种非常酷炫的多项式求和技巧，可以对某几类特殊的多项式进行运算。

非常不幸的是，小K发现老师在布置作业时抄错了数据，导致一道题并不能用刚学的方法来解，于是希望你能帮忙写一个程序跑一跑。

给出一个 $m$ 阶多项式$$f(x)=\sum_{i=0}^mb_ix^i$$

对给定的正整数 $a$ ，求$$S(n)=\sum_{k=0}^na^kf(k)$$

由于这个数可能比较大，所以你只需计算 $S(n)$ 对 $10^9+7$ 取模后的值（即计算除以 $10^9+7$ 后的余数）。

## 输入格式

从标准输入读入数据。

第一行包含三个整数 $n,m,a$。

第二行包含$m+1$个整数，$b_0,b_1,\dots,b_m$ 描述给定多项式的系数。

对于所有数据，$1\leq a,b_i\leq 10^9$。

## 输出格式

输出到标准输出。

输出一行一个数，表示 $S(n)$ 对 $10^9+7$ 取模后的结果。






## 样例1输入

```plain
5 2 3
1 1 1

```



## 样例1输出

```plain
9658

```


## 样例1解释

$f(x)=1+x+x^2$，故 $f(0)=1,f(1)=3,f(2)=7,f(3)=13,f(4)=21,f(5)=31$。

$f(0)+3f(1)+9f(2)+27f(3)+81f(4)+243f(5)=1+3*3+9*7+27*13+81*21+243*31=9658$。




## 样例2输入

```plain
100 3 233
1 2 3 4

```



## 样例2输出

```plain
994811687

```





## 样例3输入

```plain
20170314 10 11037
1 2 3 4 5 6 7 8 9 10 11

```



## 样例3输出

```plain
133604769

```


## 子任务

| 测试点      | $n$         | $m$         | $a$          |
| ----------- | ----------- | ----------- | ------------ |
| $1$ ~ $2$   | $\leq 1000$ | $\leq 10$   | $\leq 10^9$  |
| $3$         | $\leq 10^9$ | $=1$        | $=1$         |
| $4$         | $\leq 10^9$ | $=2$        | $=1$         |
| $5$         | $\leq 10^9$ | $=3$        | $\leq 10^9$  |
| $6$         | $\leq 10^9$ | $=5$        | $=1$         |
| $7$ ~ $8$   | $\leq 10^9$ | $\leq 20$   | $=1$         |
| $9$         | $\leq 10^9$ | $\leq 50$   | $\leq 10^9$  |
| $10$        | $\leq 10^9$ | $\leq 100$  | $\leq 10^9$  |