#P17650. 算

算

题目描述

有一个 mm 项多项式 p(x)p(x) 以及两个参数 cc 和 tt,其中 p(x)=a0+a1x+⋯+am−1xm−1p(x)=a_0+a_1x+\dots+a_{m-1}x^{m-1}。
定义一个新函数 s(n)s(n):

s(n)=∑i=1np(i)[gcd⁡(i,n)=1] mod 998244353s(n)=\sum_{i=1}^np(i)[\gcd(i,n)=1]\bmod 998244353

请计算 s(c),s(c2),…,s(ct)s(c),s(c^2),\dots,s(c^t)。

输入格式

第一行三个正整数,分别表示 m,c,tm,c,t。
第二行 mm 个正整数,表示 a0,a1,…,am−1a_0,a_1,\dots,a_{m-1}。

输出格式

输出 tt 行,第 ii 行一个正整数 s(ci)s(c^i)。

输入输出样例 #1

输入 #1

8 10 4
3 1 4 1 5 9 2 6

输出 #1

35683652
171899188
780914481
858211065

说明/提示

对于 10%10\% 的数据,t≤2,c≤100t\le2,c\le100;
对于 30%30\% 的数据,t≤1000,m≤1000t\le1000,m\le1000;
对于 50%50\% 的数据,t≤5⋅104,m≤5⋅104,c≤1012t\le5\cdot10^4,m\le5\cdot10^4,c\le10^{12};
对于另外 10%10\% 的数据,c=123456789c=123456789;
对于所有数据,$1\le t\le2\cdot10^5,1\le m\le2\cdot10^5,1\le c\le10^{18}$。