Background

This problem has expanded the data range compared to P9919.

Problem Description

For a bipartite graph \( G \) with \( m \) right vertices, define its weight \( w(G) \) as follows:

• Choose a matching scheme and mark the first matched right vertex. If no such vertex exists, mark the first unmatched right vertex.
• Randomly select a permutation of \( 1, 2, \cdots, m \), and stop the operation when the unmatched right vertex and the marked vertex appear as a subsequence in the permutation in order.
• \( w(G) \) is the minimum expected number of operations across all matching schemes.

Define the bipartite graph \( G \) as \( k \)-legal if and only if:

• The degree of all left vertices is between \( k \) and \( 2 \).
• No two left vertices have the same set of adjacent vertices.

Define \( f(k, x) \) as the sum of \( w(G) \) for all \( k \)-legal bipartite graphs \( G \) with \( x \) right vertices, where the left vertices are not distinguished.

Given \( n, k, a_{0 \sim n} \), find \( \sum_{i=0}^n a_i f(k, i) \bmod 998244353 \).

Input Format

One line containing two positive integers, \( n \) and \( k \).

The second line contains \( n+1 \) non-negative integers, \( a_{0 \sim n} \).

Output Format

One line containing a non-negative integer, representing the answer.

Sample Input and Output

Sample Input #1

2 1
1 1 1

Sample Output #1

15

Sample Input #2

3 2
1 1 1 1

Sample Output #2

40

Sample Input #3

12 1
1 1 4 5 1 4 1 9 1 9 8 1 0

Sample Output #3

721168027

Notes

A left vertex connected to right vertices with indices \( x, y \) is denoted as \( (x, y) \).

Sample 1 Explanation

For \( n = 0, 1 \), the answers are obviously \( 1, 2 \).

For \( n = 2 \), possible bipartite graphs (represented by tuples of adjacent vertices for each left vertex) are:

\( () \)

\( (1), (2), (1, 2) \)

\( \{(1), (2)\}, \{(1, 2), (2)\}, \{(1, 2), (1)\}, \{(1, 2), (1), (2)\} \)

Bipartite graphs with the same expectation are grouped together. The answer is \( \frac{2}{1} + \frac{2}{1} \times 3 + \frac{2}{2} \times 4 = 12 \), and the output is \( 1 \times 1 + 1 \times 2 + 1 \times 12 = 15 \).

Sample 2 Explanation

For \( n = 0, 1, 2 \), the answers are \( 1, 1, 4 \).

For \( n = 3 \), possible bipartite graphs (represented by tuples of adjacent vertices for each left vertex) are:

\( () \)

\( (1, 2), (1, 3), (2, 3) \)

\( \{(1, 2), (1, 3)\}, \{(1, 2), (2, 3)\}, \{(1, 3), (2, 3)\} \)

\( \{(1, 2), (2, 3), (1, 3)\} \)

The answer is \( \frac{6}{1} + \frac{6}{1} \times 3 + \frac{6}{2} \times 3 + \frac{6}{6} = 34 \).

Data Range

For \( 100\% \) of the data, \( 0 \le n \le 10^5 \), \( 1 \le k \le 2 \), \( 0 \le a_i < 998244353 \).

见题面 Input 部分

见题面 Output 部分