Problem Background

KDOI has expanded its business to the moon. However, the internet speed on the moon is very slow, and they need to address this issue.

KDOI's staff has developed a new type of wireless LAN module called Wife (WIreless Fidelity Extend). Each module can connect to at most two users and can provide 1 unit of bandwidth to one of them. Regardless of how many modules provide bandwidth to a single user, their total bandwidth remains 1.

The company's employees are very lazy and often delay their work for a month. Therefore, they are also too lazy to label the Wife modules, meaning all modules are indistinguishable. Additionally, to save on electricity costs, no two modules can have the same working customer range.

Currently, there are $n$ users who have purchased the service. When the Wife system is officially launched, the router discovers a problem: some users may not have broadband available! Kaito now has no Wife modules and can only seize one, sacrificing the interests of one user, and allocate it to all users including those with broadband in a certain order. However, users without broadband are very demanding, and if they are not provided with broadband in a continuous sequence according to their registration order, they will threaten to demand a refund from the router.

Kaito has forgotten their registration times and can only randomly select a permutation from $1$ to $n$ to determine the order of providing broadband. To minimize the number of attempts, he will adjust the connections of the Wife modules. He wants to know the minimum expected number of attempts needed to appease these customers.

Specifically, there are two types of Wife modules. Type 1 can choose to connect to only one user, while Type 2 can only connect to two different users. You need to calculate the answers for both types.

Kaito himself certainly won't do it, so he asks you to find the results $ans_i$ for all $i \in [0, n]$. Considering that reporting one by one would be exhausting, the benevolent router will provide you with an array $a$, and you need to output $\sum a_i \times ans_i$.

Problem Description

Formal Problem Statement

For a bipartite graph $G$ with $m$ right vertices, define its value $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 vertices and the marked vertex appear as a subsequence in the permutation.
• $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:

• All left vertices have degrees 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 and indistinguishable left vertices.

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

Input and Output Format

Input Format

One line with two positive integers, representing $n$ and the type $k$ of Wife.

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

Output Format

One line with 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

Denote a left vertex connected to right vertices with numbers $x, y$ 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$, output $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 1.5 \times 10^4$, $1 \le k \le 2$, $0 \le a_i < 998244353$.

This problem has subtask-based scoring.

见题面 Input 部分

见题面 Output 部分