[W1] 算
题目描述
有一个 $m$ 项多项式 $p(x)$ 以及两个参数 $c$ 和 $t$，其中 $p(x)=a_0+a_1x+\dots+a_{m-1}x^{m-1}$。
定义一个新函数 $s(n)$:
$$s(n)=\sum_{i=1}^np(i)[\gcd(i,n)=1]\bmod 998244353$$
请计算 $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)$。
输入输出样例
输入样例 #1
8 10 4
3 1 4 1 5 9 2 6输出样例 #1
35683652
171899188
780914481
858211065说明
对于 $10\%$ 的数据，$t\le2,c\le100$;
对于 $30\%$ 的数据，$t\le1000,m\le1000$；
对于 $50\%$ 的数据，$t\le5\cdot10^4,m\le5\cdot10^4,c\le10^{12}$；
对于另外 $10\%$ 的数据，$c=123456789$；
对于所有数据，$1\le t\le2\cdot10^5,1\le m\le2\cdot10^5,1\le c\le10^{18}$。