Background

Compared with P9919, this problem has a larger Constraints range.

Problem Description

For a bipartite graph $G$ with $m$ vertices on the right side, define its weight $w(G)$ as follows:

• Choose a matching scheme, and mark the first matched right-side vertex. If no such vertex exists, then mark the first unmatched right-side vertex.
• Each time, randomly choose a permutation of $1,2,\cdots,m$. Stop when the unmatched right-side vertices and the marked vertex appear as a contiguous segment in the permutation in increasing label order.
• $w(G)$ is the minimum value of the expected number of operations over all matching schemes.

Define this bipartite graph $G$ to be $k$-valid if and only if:

• The degree of every left-side vertex is between $k$ and $\color{red}2$.
• There do not exist two different left-side vertices whose sets of adjacent vertices are identical.

Let $f(k,x)$ be the sum of $w(G)$ over all $k$-valid bipartite graphs $G$ with $x$ right-side vertices, where left-side vertices are not distinguished.

Given $n,k,a_{0\sim n}$, compute $\sum\limits^n_i a_i f(k,i) \bmod998244353$.

Input Format

The first line contains two positive integers $n,k$.

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

Output Format

Output one non-negative integer, the answer.

2 1
1 1 1

15

3 2
1 1 1 1

40

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

721168027

Hint

By convention, a left-side vertex connected to right-side vertices numbered $x,y$ is denoted as $(x,y)$.

[Sample 1 Explanation]

For $n=0,1$, the answers are clearly $1,2$.

For $n=2$, the possible bipartite graphs are (represented by the tuple formed by the neighbors of each left-side vertex):

$()$

$(1),(2),(1,2)$

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

Graphs with the same expectation are grouped together. The answer is $\dfrac21+\dfrac21\times3+\dfrac22\times4=12$, so the output is $1\times1+1\times2+1\times12=15$.

[Sample 2 Explanation]

For $n=0,1,2$, the answers are $1,1,4$.

For $n=3$, the possible bipartite graphs are (represented by the tuple formed by the neighbors of each left-side vertex):

$()$

$(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 $\dfrac61+\dfrac61\times3+\dfrac62\times3+\dfrac66=34$.

[Constraints]

For $100\%$ of the testdata, $0\le n\le10^5$, $1\le k\le2$, $0\le a_i<998244353$.

Translated by ChatGPT 5