给定多项式 F(z)=∑n−1i=0fizi 与 m 个非负整数 x1,x2,⋯,xm。对每个 1≤i≤m 你需要计算 f(xi) 的值。
输入格式
第一行两个整数 n,m,描述多项式的次数为 n−1 次,询问的数量为 m。
接下来一行 n 个整数 f0,f1,⋯,fn−1
接下来 m 行,每行一个整数 xi,描述一组询问。
输出格式
输出 m 行,每行一个整数,描述询问取模 998,244,353 后的结果。
样例数据
样例输入
6 6
1 1 4 5 1 4
1
19
191
1919
810
1919810
样例输出
16
10070476
934460929
474354141
579687411
895765304
子任务
对于所有数据,1≤n,m≤106。
测试点 | n,m |
---|---|
1 | 100 |
2 | 5×103 |
3 | 3×104 |
4 | 105 |
5 | 106 |