Migrated from Lutece 2746 Rust

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

纯音乐，请您欣赏。
——《Rust》

---

有一 $m$ 阶多项式

$$f(x)=\sum_{i=0}^m b_ix^i$$

对于给定正整数 $a,n$，求

$$S(n)=\sum_{k=0}^n a^kf(k)$$

的值，对 $10^9+7$ 取模。

Input

第一行三个正整数 $n,m,a\ (1\le n,a\le 10^9,1\le m\le 5\times 10^3)$。

第二行 $m+1$ 个整数 $b_0,b_1,\ldots, b_m\ (0\le b_i<10^9+7)$，表示多项式的系数。保证 $b_m\neq 0$。

Output

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

Samples

5 1 4
1 1

7737

Note

多项式为

$$f(x)=x+1$$

则

$$\begin{aligned} S(5)&=\sum_{k=0}^5 4^kf(k)\\ &=4^0f(0)+4^1f(1)+4^2f(2)+4^3f(3)+4^4f(4)+4^5f(5)\\ &=1\times 1+4\times 2+16\times 3+64\times 4+256\times 5+1024\times 6\\ &=7737 \end{aligned} $$

Resources

2022 UESTC ICPC Training for Math and Geometry