题目背景

  「       ，       」

---

  “你非说这不是我的实力，那凭什么一个偶然错音就不能毁了我的命运？！”

  天依没有注意到，心中所哭嚎向的那个人，同她一样撑着伞，身后十来步而已。

---

  清明　「你在名为弱小的深渊　究竟看见过什么」

题目描述

雨打在窗沿，下坠，一级一级。

这里一共有 $n$ 级窗沿，从高到低编号，最高层编号为 $1$，最底层编号为 $n$。假设在某一瞬间，第 $i$ 级窗沿上有 $a_i$ 单位体积的雨水。由于奇妙的物理原因，第 $i$ 级的雨水将在「下一个瞬间」滴向第 $i+1,i+2,\dots,\min\{i+k,n\}$ 级，也可能留在第 $i$ 级，但是每一种去向的雨水的单位体积都应是非负整数，且总和为 $a_i$。

设在「下一个瞬间」，第 $i$ 级窗沿上有 $a_i'$ 单位的雨水，那么称此时雨水的奇妙度为 $\prod_{i=1}^n a_i'$。现在，悲伤的人儿想知道，对于所有本质不同的「下一个瞬间」，雨水的奇妙度之和对素数 $P=998244353$ 取模的结果。

两个「下一个瞬间」本质不同，当且仅当存在编号 $i<j$ 的两级窗沿，从窗沿 $i$ 滴向窗沿 $j$ 的雨水的单位体积不同。

输入格式

第一行输入两个正整数 $n,k$，分别表示窗沿的数量、限制雨点滴落距离的常数。

第二行输入 $n$ 个非负整数 $a_1,a_2,a_3,\cdots,a_n$，其中 $a_i$ 表示第 $i$ 级窗沿在这一瞬间的雨水体积。

输出格式

输出一行一个整数，表示所有本质不同的「下一个瞬间」，雨水的奇妙度之和对 $P$ 取模后的结果。

3 0
2 2 2

8

3 1
2 2 2

30

5 3
2 3 4 4 3

275200

提示

样例 #1 解释

容易发现总共只有一种本质不同的「下一个瞬间」，也就是每级窗沿都没有雨水向其他窗沿滴落。

所以最终 $a'=\{2,2,2\}$，权值为 $8$。

样例 #2 解释

设 $c_k$ 表示从第 $k$ 级窗沿滴向第 $k+1$ 级窗沿的雨点体积，显然有 $c_3=0$。

枚举所有合法的滴落情况：

• $c=\{0,0,0\},b=\{2,2,2\}$，权值为 $8$；
• $c=\{0,1,0\},b=\{2,1,3\}$，权值为 $6$；
• $c=\{0,2,0\},b=\{2,0,4\}$，权值为 $0$；
• $c=\{1,0,0\},b=\{1,3,2\}$，权值为 $6$；
• $c=\{1,1,0\},b=\{1,2,3\}$，权值为 $6$；
• $c=\{1,2,0\},b=\{1,1,4\}$，权值为 $4$；
• $c_1=2$，此时必然有 $b_1=0$，此情况下的三种方案权值均为 $0$；

所以所有本质不同的「下一个瞬间」的权值和为 $8+6+0+6+6+4+0+0+0=30$。

数据规模与约定

本题采用 Subtask 的计分方式。

对于 $100\%$ 的数据，$0\le k<n\le 32$，$0\le a_i<P$。

对于不同的子任务，作如下约定：

子任务编号	$n$	$k$	$\max a_i$	子任务分值
$1$	$\le32$	$<n$	$=0$	$2$
$2$		$=0$	$<P$
$3$		$<n$	$=1$	$3$
$4$	$\le5$		$\le4$	$20$
$5$	$\le32$	$=1$	$<P$	$13$
$6$		$=n-1$		$10$
$7$		$\le16$		$20$
$8$	$\le25$	$<n$		$10$
$9$	$\le32$			$20$