题目背景

本题相较于 P9919 扩大了数据范围。

题目描述

对于一个右部点为 $m$ 个的二分图 $G$，定义它的权值 $w(G)$ 如下：

• 选择一种匹配方案，标记第一个已匹配的右部点。如果不存在这样的点，那么标记第一个未匹配的右部点。
• 每次随机选择一个 $1,2,\cdots,m$ 的排列，当未匹配的右部点与被标记的点 按标号顺序作为一个子段出现在排列中时 停止操作。
• $w(G)$ 为在所有匹配方案中操作次数期望的 最小值。

将这个二分图 $G$ 定义为 $k$ 合法 的，当且仅当：

• 所有左部点的度数在 $k\sim 2$ 之间。
• 没有任意两个左部点，与其相邻的点组成的集合相同。

定义 $f(k,x)$ 为所有右部点 $x$ 个，左部点不进行区分的 $k$ 合法二分图 $G$ 的 $w(G)$ 之和。

给定 $n,k,a_{0\sim n}$，求 $\sum\limits^n_ia_if(k,i) \bmod998244353$。

输入格式

一行两个正整数，分别表示 $n,k$。

第二行 $n+1$ 个非负整数，分别表示 $a_{0\sim n}$。

输出格式

一行一个非负整数，表示答案。

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

提示

约定一个左部点连接了编号为 $x,y$ 的右部点表示为 $(x,y)$。

【样例 1 解释】

对于 $n=0,1$，答案显然为 $1,2$。

对于 $n=2$，可能的二分图为（用每个左部点的邻接点组成的元组表示）：

$()$

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

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

期望相同的二分图被分为一组。答案为 $\dfrac21+\dfrac21\times3+\dfrac22\times4=12$，输出 $1\times1+1\times2+1\times12=15$。

【样例 2 解释】

对于 $n=0,1,2$，答案为 $1,1,4$。

对于 $n=3$，可能的二分图为（用每个左部点的邻接点组成的元组表示）：

$()$

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

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

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

答案为 $\dfrac61+\dfrac61\times3+\dfrac62\times3+\dfrac66=34$。

【数据范围】

对于 $100\%$ 的数据，$0\le n\le10^5$，$1\le k\le2$，$0\le a_i<998244353$。