题目描述

有一个 $m$ 项多项式 $p(x)$ 以及两个参数 $c$ 和 $t$，其中 $p(x)=a_0+a_1x+\dots+a_{m-1}x^{m-1}$。 定义一个新函数 $s(n)$:

请计算 $s(c),s(c^2),\dots,s(c^t)$。

输入格式

第一行三个正整数，分别表示 $m,c,t$。 第二行 $m$ 个正整数，表示 $a_0,a_1,\dots,a_{m-1}$。

输出格式

输出 $t$ 行，第 $i$ 行一个正整数 $s(c^i)$。

8 10 4
3 1 4 1 5 9 2 6

35683652
171899188
780914481
858211065

数据规模与约定

对于 $10\%$ 的数据，$t\le2$，$c\le100$; 对于 $30\%$ 的数据，$t\le10^3$，$m\le10^3$； 对于 $50\%$ 的数据，$t\le5\times 10^4$，$m\le5\times 10^4$，$c\le10^{12}$； 对于另外 $10\%$ 的数据，$c=123456789$； 对于所有数据，$1\le t\le2\times 10^5$，$1\le m\le2\times 10^5$，$1\le c\le10^{18}$。

作者

在Hydro OJ 复活，已被允许，作者见上方