我爱数树

题目描述

给定一个长度为 $n$ 的权值数组 $w_0,w_1,\dots,w_{n-1}$。

对于一棵有根树 $T=(V,E)$，记 $s_i$ 为节点 $i$ 的儿子个数，定义这棵树的权值为 $\prod_{i\in V} w_{s_i}$。

给定两个正整数 $n,k$，如果点集 $\{1,2,\dots,k\}$ 在树 $T$ 上导出子图是连通的，则称这棵树是好的。

你需要求出所有节点标号为 $1,2,\dots,n$、以 $1$ 为根的好的有标号有根树 $T$ 的权值之和。答案对 $998244353$ 取模。

输入格式

第一行，两个正整数 $n,k$（$1\le k\le n\le 2\times 10^5$），分别表示树的大小与限制集合大小。

第二行，$n$ 个非负整数 $w_0,w_1,\dots,w_{n-1}$（$0\le w_i<998244353$），表示给定的权值数组。

输出格式

输出一行，一个整数，表示所有满足条件的有标号有根树的权值之和对 $998244353$ 取模后的结果。

样例

样例输入 1

4 2
1 2 3 4

样例输出 1

50

样例输入 2

6 3
1 1 4 5 1 4

样例输出 2

2662