Background

(The picture is from a Phigros music illustration. Please contact for removal if there is any infringement.)

Link to the harder version

KDOI’s business has expanded to the Moon. However, the Internet speed on the Moon is very slow, so they need to solve the network speed problem.

KDOI’s staff have developed a new type of wireless LAN module, Wife (WIreless Fidelity Extend). Each module can connect to at most two users, and it can choose to provide $1$ unit of bandwidth to one of the connected users. However, no matter how many modules provide bandwidth to the same user at the same time, the user’s total bandwidth is always $1$.

The employees are very lazy, often delaying a PPT for a whole month. So they are also too lazy to label the Wife modules, meaning all modules are indistinguishable from each other. In addition, to save electricity, no two modules are allowed to have exactly the same set of users they serve.

Now there are $n$ users who purchased the service. When the Wife system officially starts, the router (Lu-you-qi) finds a problem: some users may have no broadband to use. Kaitou has no Wife modules in hand, so he can only grab one, sacrifice one user’s interests, and provide broadband to all users who have broadband in a certain order. However, the users without broadband are very demanding: as long as they are not provided broadband consecutively in their registration order, they will threaten the router to refund.

Kaitou has already forgotten their registration times, so he can only randomly choose a permutation of $1\sim n$ to decide the order of providing broadband. To minimize the number of attempts, he will adjust which users are connected by Wife. He wants to know the minimum expected number of attempts needed to calm the customers’ anger.

In particular, Wife has two models. Model $1$ may choose to connect to only one user, while model $2$ must connect to two different users. You need to compute the answers for both models separately.

Kaitou surely won’t will do it himself, so he asks you to compute the result $ans_i$ for all $i\in[0,n]$. Considering that you would be exhausted if you reported them one by one, the kind router will give you an array $a$, and you only need to output $\sum a_i\times ans_i$.

Problem Description

Formal statement

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

• Choose a matching, 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 subsegment in the permutation in increasing label order.
• $w(G)$ is the minimum expected number of operations among all matchings.

Call this bipartite graph $G$ $k$-legal if and only if:

• Every left-side vertex has degree between $k$ and $2$.
• For any two left-side vertices, the sets of their adjacent vertices are not identical.

Define $f(k,x)$ as the sum of $w(G)$ over all $k$-legal bipartite graphs $G$ with $x$ right-side vertices, where left-side vertices are indistinguishable.

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

Input Format

The first line contains two positive integers $n$ and the Wife model $k$.

The second line contains $n+1$ non-negative integers $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 written as $(x,y)$.

Explanation of Sample 1

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

For $n=2$, the possible bipartite graphs are (each left-side vertex is represented by the tuple of its adjacent vertices):

$()$

$(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\times 3+\dfrac22\times 4=12$, so the output is $1\times 1+1\times 2+1\times 12=15$.

Explanation of Sample 2

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

For $n=3$, the possible bipartite graphs are (each left-side vertex is represented by the tuple of its adjacent vertices):

$()$

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

Constraints

For $100\%$ of the testdata, $0\le n\le 1.5\times 10^4$, $1\le k\le 2$, and $0\le a_i<998244353$.

This problem uses bundled testcases.

Translated by ChatGPT 5