Problem Description

Given a polynomial \( f(n) \) and a rational number \( r \) within the interval \( (0,1) \), compute the sum \( \sum_{n=0}^{\infty} f(n) r^n \). If the simplest form of the answer is \( \frac{p}{q} \), you only need to output the value of \( p \times q^{-1} \mod 998244353 \).

Input Format

The first line contains two integers \( m \) and \( r \), where \( m \) is the degree of the polynomial.

The second line contains \( m+1 \) integers, where the \( i \)-th integer is the coefficient \( a_{i-1} \) of \( x^{i-1} \).

Output Format

Output a single number, which is the answer.

Sample Input and Output

Sample Input #1

1 499122177
0 1

Sample Output #1

2

Sample Input #2

2 748683265
0 0 1

Sample Output #2

628524223

Sample Input #3

3 713031681
7 5 23 2

Sample Output #3

257147786

Notes

For \( 10\% \) of the data, \( m \le 5 \).

For \( 40\% \) of the data, \( m \le 2000 \).

For \( 100\% \) of the data, \( m \le 10^5 \), \( a_i \in [0, 998244353) \), and it is guaranteed that \( a_m \neq 0 \).

Bundled Testing

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} \)

见题面 Input 部分

见题面 Output 部分