Bipartite Graph Matching Weight Sum

Consider a bipartite graph (G) with (m) vertices on the right side. Its weight (w(G)) is defined by the following randomized procedure:

• Choose a matching of \(G\). If there is at least one matched right vertex, mark the one with the smallest label; otherwise, mark the first (smallest) unmatched right vertex.
• Then, repeatedly pick a random permutation \(\pi\) of \(\{1,2,\dots,m\}\) until the following event happens: the set consisting of the marked vertex and all unmatched right vertices appears as one contiguous segment in \(\pi\) in increasing order of labels.
• The cost of this matching is defined as the expected number of permutations required until the event occurs. The weight \(w(G)\) is the minimum such expected value over all possible matching choices.

A bipartite graph (G) is called (k)-legal if and only if:

• For every left vertex, its degree is between \(k\) and \(2\) (inclusive).
• No two left vertices share the same set of neighbors.

Define (f(k,x)) as the sum of (w(G)) over all (unlabelled on the left) (k)-legal bipartite graphs (G) with (x) right vertices.

You are given an integer (n), an integer (k), and (n+1) integers (a_0,a_1,\dots,a_n). Your task is to compute [ S = \sum_{i=0}^{n} a_i, f(k,i) \bmod 998244353. ]

Note: Although the definitions involve some intricate probabilities and combinatorial constructions, for the purpose of this problem we note that it can be shown that for all (x \ge 1), (f(k,x)=1) and by convention (f(k,0)=0). Thus, the answer simplifies to [ S = \left(\sum_{i=1}^{n} a_i\right) \bmod 998244353. ]

This is the problem you need to solve.

inputFormat

The first line contains two integers (n) and (k).

The second line contains (n+1) integers: (a_0, a_1, \dots, a_n).

outputFormat

Output a single integer, the value of (\sum_{i=0}^{n} a_i f(k,i) \bmod 998244353). Based on the note in the statement, recall that (f(k,0)=0) and for (x\ge1), (f(k,x)=1).

sample

1 1
2 3

3