时间限制： 1.0 秒

空间限制： 512 MB

题目背景

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

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

题目描述

给出一个 $m$ 阶多项式

对给定的正整数 $a$，求

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

输入格式

从标准输入读入数据。

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

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

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

输出格式

输出到标准输出。

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

5 2 3
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 \times 3 + 9 \times 7 + 27 \times 13 + 81 \times 21 + 243 \times 31 = 9658$。

100 3 233
1 2 3 4

994811687

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

133604769

子任务