Description

$$\text{Find}\ \sum_{n=0}^{\infty}f(n)\ r^n\ ,\ f(n)\text{ is a polynomial},\ r\text{ is a rational number in }(0,1)$$

If the simplest fraction form of the answer is $\frac{p}{q}$, you only need to output the value of $p\times q^{-1}\ \mathrm{mod}\ 998244353$.

Input Format

The first line contains two integers $m, r$. $m$ is the degree of the polynomial.

The second line contains $m+1$ integers. The $i$-th integer is the coefficient $a_{i-1}$ of $x^{i-1}$.

Output Format

Only one line with one number, which is the answer.

1 499122177
0 1

2

2 748683265
0 0 1

628524223

3 713031681
7 5 23 2

257147786

Hint

For $10\%$ of the testdata, $m\le 5$.

For $40\%$ of the testdata, $m\le 2000$.

For $100\%$ of the testdata, $m\le 10^5\ ,\ a_i\in [0,998244353)$, and it is guaranteed that $\ a_{m}\neq 0$.

Bundled Tests

---

Sample 1 Explanation:

$499122177\equiv \frac{1}{2}\ (\mathrm{mod}\ 998244353)$.

$\sum_{n=0}^{\infty}n\ (\frac{1}{2})^n=2$.

---

Sample 2 Explanation:

$748683265\equiv \frac{1}{4}\ (\mathrm{mod}\ 998244353)$.

$\sum_{n=0}^{\infty}n^2\ (\frac{1}{4})^n=\frac{20}{27}$.

---

Sample 3 Explanation:

$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}$.

Translated by ChatGPT 5