Polynomial
时间限制： 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输入
5 2 3
1 1 1
样例1输出
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输入
100 3 233
1 2 3 4
样例2输出
994811687
样例3输入
20170314 10 11037
1 2 3 4 5 6 7 8 9 10 11
样例3输出
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\) |