{"raw_statement":[{"iden":"background","content":"![](https://cdn.luogu.com.cn/upload/image_hosting/hi1cu7o7.png)\n\n（图片来自 phigros 曲绘，侵删。）\n\n[加强版链接](/problem/P10286)\n\nKDOI 的业务发展到月亮上了。但是月亮上网速很慢，他们需要解决网速问题。\n\nKDOI 的工作人员研发了一种新型无线局域网模块 Wife（WIreless Fidelity Extend），每个模块最多连接两个用户，并且可以选择为其中一位客户提供 $1$ 单位带宽。不过，无论有多少个模块同时为一位客户提供带宽，他的总带宽永远是 $1$。\n\n公司的员工都很懒，经常 ppt 一鸽就是一个月。因此，他们也懒得为 Wife 贴上标签，也就是所有模块间不做区分。另外，为了节省电费，不能有两个模块的工作客户范围完全相同。\n\n现在有 $n$ 个用户购买了服务。当 Wife 系统正式启动时，鹿由器发现了一个问题：可能有些用户没有宽带可以使用！快斗现在手里没有 Wife，只能抢来一个，牺牲一个用户的利益，按一定顺序给所有包括有宽带的用户使用。然而，没有宽带的用户们要求很苛刻，只要没有给他们按注册顺序连续地提供宽带，他们就会威胁鹿由器退钱。\n\n快斗已经忘了他们的注册时间了，只能随机选一个 $1\\sim n$ 的排列来决定提供宽带的顺序。为了让尝试的次数尽量小，他会调整 Wife 连接的用户。他想知道，要让这些顾客平息愤怒，需要尝试的最小期望次数是多少。\n\n特别的，Wife 有两种型号。型号 $1$ 可以选择只连接一位，型号 $2$ 则只能连接两个不同客户。你需要分别计算出这两种型号的答案。\n\n快斗自己肯定~~不~~会做，所以他要让你求出所有 $i\\in[0,n]$ 的结果 $ans_i$。考虑到你如果一个一个汇报会累死的，仁慈的鹿由器会给你数组 $a$，让你输出 $\\sum a_i\\times ans_i$。\n\n"},{"iden":"statement","content":"#### 【形式化题意】\n\n对于一个右部点为 $m$ 个的二分图 $G$，定义它的权值 $w(G)$ 如下：\n\n- 选择一种匹配方案，标记第一个已匹配的右部点。如果不存在这样的点，那么标记第一个未匹配的右部点。\n- 每次随机选择一个 $1,2,\\cdots,m$ 的排列，当未匹配的右部点与被标记的点 **按标号顺序作为一个子段出现在排列中时** 停止操作。\n- $w(G)$ 为在所有匹配方案中操作次数期望的 **最小值**。\n\n将这个二分图 $G$ 定义为 **$k$ 合法** 的，当且仅当：\n\n- 所有左部点的度数在 $k\\sim 2$ 之间。\n- 没有任意两个左部点，与其相邻的点组成的集合相同。\n\n定义 $f(k,x)$ 为所有右部点 $x$ 个，左部点不进行区分的 $k$ 合法二分图 $G$ 的 $w(G)$ 之和。\n\n给定 $n,k,a_{0\\sim n}$，求 $\\sum\\limits^n_ia_if(k,i) \\bmod998244353$。"},{"iden":"input","content":"一行两个正整数，分别表示 $n$ 与 Wife 的型号 $k$。\n\n第二行 $n+1$ 个非负整数，分别表示 $a_{0\\sim n}$。"},{"iden":"output","content":"一行一个非负整数，表示答案。"},{"iden":"note","content":"约定一个左部点连接了编号为 $x,y$ 的右部点表示为 $(x,y)$。\n\n#### 【样例 1 解释】\n\n对于 $n=0,1$，答案显然为 $1,2$。\n\n对于 $n=2$，可能的二分图为（用每个左部点的邻接点组成的元组表示）：\n\n$()$\n\n$(1),(2),(1,2)$\n\n$\\{(1),(2)\\},\\{(1,2),(2)\\},\\{(1,2),(1)\\},\\{(1,2),(1),(2)\\}$\n\n期望相同的二分图被分为一组。答案为 $\\dfrac21+\\dfrac21\\times3+\\dfrac22\\times4=12$，输出 $1\\times1+1\\times2+1\\times12=15$。\n\n#### 【样例 2 解释】\n\n对于 $n=0,1,2$，答案为 $1,1,4$。\n\n对于 $n=3$，可能的二分图为（用每个左部点的邻接点组成的元组表示）：\n\n$()$\n\n$(1,2),(1,3),(2,3)$\n\n$\\{(1,2),(1,3)\\},\\{(1,2),(2,3)\\},\\{(1,3),(2,3)\\}$\n\n$\\{(1,2),(2,3),(1,3)\\}$\n\n答案为 $\\dfrac61+\\dfrac61\\times3+\\dfrac62\\times3+\\dfrac66=34$。\n\n#### 【数据范围】\n\n对于 $100\\%$ 的数据，$0\\le n\\le1.5\\times10^4$，$1\\le k\\le2$，$0\\le a_i<998244353$。\n\n**本题开启捆绑测试**\n\n|$\\text{Subtask}$|$\\text{Score}$|$n\\le $|$k\\ge$|特殊性质|\n|:-:|:-:|:-:|:-:|:-:|\n|$0$|$5$|$5$|$1$||\n|$1$|$10$|$500$|$2$||\n|$2$|$20$|$500$|$1$|$a_i\\equiv\\dfrac1{i!}$|\n|$3$|$20$|$1.5\\times10^4$|$2$|$a_i\\equiv\\dfrac1{i!}$|\n|$4$|$45$|$1.5\\times10^4$|$1$||"}],"translated_statement":null,"sample_group":[["2 1\n1 1 1","15"],["3 2\n1 1 1 1","40"],["12 1\n1 1 4 5 1 4 1 9 1 9 8 1 0","721168027"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}