童话只美在真实却从不续写。
泠珞最近学习了前缀和算法,她写出了以下程序:
read(n),read(a);
for(int i=0;i<=n;i++)read(f[i]);
for(int t=1;t<=n;t++){
for(int i=1;i<=n;i++)f[i]=f[i]+a*f[i-1];
ans[t]=f[t];
}
她发现这个程序在 n 比较大的时候会运行超时,请你帮忙写一个程序帮她计算出 ans1,ans2,⋯,ansn,由于答案数值过大,你只需告诉她每个数除以 998244353 的余数。
输入格式
第一行两个正整数 n,a。
接下来一行 n+1 个非负整数,表示 f0,f1,⋯,fn。
输出格式
n 个非负整数,表示 ans1,ans2,⋯,ansn。
样例
样例 #1:
输入:
2 1
1 2 0
输出:
3 7
样例 #2:
输入:
10 10
5 9 7 8 0 6 3 2 4 10 1
输出:
59 1687 55618 1937320 69557006 549579657 621247830 250099579 483510144 968467040
数据范围与约定
对于 100% 的数据,保证 2⩽。
子任务编号 | n\leqslant | 特殊性质 | 分值 |
---|---|---|---|
1 | 2000 | 5 | |
2 | 10^5 | A | 5 |
3 | 10^5 | BC | 5 |
4 | 10^5 | BD | 10 |
5 | 10^5 | C | 10 |
6 | 5\times10^4 | 10 | |
7 | 10^5 | 10 | |
8 | 2\times 10^5 | 15 | |
9 | 5\times 10^5 | 15 | |
10 | 10^6 | 15 |
特殊性质 A:保证 f_i\ne 0 的 i 数量不超过 100 。
特殊性质 B:保证 a=1 。
特殊性质 C:保证对于所有 i\in[0,n] ,都满足 f_i=1 。
特殊性质 D:保证对于所有 i\in[0,n] ,都满足 f_i={i+2\choose 2}=\frac{(i+2)(i+1)}{2} 。