Sum of Weighted k‑Legal Bipartite Graphs

Consider a bipartite graph \(G\) with \(m\) right vertices. For \(G\), a weight \(w(G)\) is defined via the following randomized process:

• Choose a matching scheme and mark the first matched right vertex. If none is matched, mark the first unmatched right vertex.
• Independently, repeatedly generate a random permutation of \(\{1,2,\dots,m\}\). Stop when the marked vertex and all unmatched right vertices appear as a contiguous segment in the permutation in increasing order.
• Let \(w(G)\) be the minimum expected number of operations over all possible matching schemes.

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

• Every left vertex has a degree between \(k\) and \(2\) (inclusive).
• No two left vertices have the same set of neighboring right vertices.

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

It can be shown that under the conditions of this problem, \(w(G)=1\) for every \(k\)-legal bipartite graph \(G\) (and hence \(f(k,x)=1\) for every \(x\)). Your task is to compute

[ S = \sum_{i=0}^{n} a_i \cdot f(k,i) \equiv \sum_{i=0}^{n} a_i \pmod{998244353}, ]

given an integer \(n\), an integer \(k\), and \(n+1\) integers \(a_0, a_1, \dots, a_n\).

inputFormat

The first line contains two integers \(n\) and \(k\) (where \(0 \leq n \leq \text{some upper bound}\) and \(k\) is an integer parameter).

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

outputFormat

Output a single integer: the value of \(\sum_{i=0}^{n} a_i \pmod{998244353}\).

sample

0 1
10

10