题目背景

来到数学院劳动

题目描述

$$\text{求}\ \sum_{n=0}^{\infty}f(n)\ r^n\ ,\ f(n)\text{为一个多项式},\ r\text{是一个}(0,1)\text{内的有理数}$$ 若答案的最简分数为$\frac{p}{q}$,你只需要输出$p\times q^{-1}\ \mathrm{mod} \ 998244353\ $的值即可。

输入输出格式

输入格式


第一行两个整数$m,r$。$m$为多项式的次数。 第二行$m+1$个整数,第$i$个为$x^{i-1}$的系数$a_{i-1}$。

输出格式


仅一行一个数字,为答案。

输入输出样例

输入样例 #1

1 499122177
0 1

输出样例 #1

2

输入样例 #2

2 748683265
0 0 1

输出样例 #2

628524223

输入样例 #3

3 713031681
7 5 23 2

输出样例 #3

257147786

说明

对于$10\%$的数据,$m\le 5$。 对于$40\%$的数据,$m\le 2000$。 对于$100\%$的数据,$m\le 10^5\ ,\ a_i\in [0,998244353)$,保证$\ a_{m}\neq 0$ **捆绑测试** ---- **样例1解释:** $499122177\equiv \frac{1}{2}\ (\mathrm{mod}\ 998244353)$ $\sum_{n=0}^{\infty}n\ (\frac{1}{2})^n=2$ ----- **样例2解释:** $748683265\equiv \frac{1}{4}\ (\mathrm{mod}\ 998244353)$ $\sum_{n=0}^{\infty}n^2\ (\frac{1}{4})^n=\frac{20}{27}$ ----- **样例3解释:** $713031681\equiv \frac{2}{7}\ (\mathrm{mod}\ 998244353)$ $\sum_{n=0}^{\infty}(2n^3+23n^2+5n+7)\ (\frac{2}{7})^n=\frac{25417}{625}$