You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

绘画（$\texttt{draw}$）

【题目描述】

露娜和朝日喜欢绘画。

现在有一张长度为 $n$ 的画布，有 $n$ 个格子从左到右排成一排。

现在露娜要选择一些格子，然后让朝日在这些格子上涂色，其中第 $i$ 个格子有 $a_i$ 种颜色可以涂。

但露娜是个对美感有特殊追求的人，她认为有些格子不能同时涂色，不然就不美了，具体来说，满足如下两个条件的方案才是美的：

• 任意相邻的两个格子不能同时被涂色。
• 任意距离为 $k$ 的两个格子不能同时被涂色（即任意 $i,i+k$ 不能同时被涂色）。

显然露娜不可能选出一种不美的方案给朝日涂色，她所选的格子一定满足上面的两个条件。

现在你想知道她们总共能画出多少幅不同的画，两幅画不同当且仅当某个格子在一种方案上被涂色了而在另一种方案中没有，或者在两种方案中被染成了不同的颜色。

求不同的涂色方案数，对 $998244353$ 取模。

【输入格式】

从 $\texttt{draw.in}$ 中读入数据。

第一行两个整数 $n,k$。

第二行 $n$ 个整数表示 $a_1,a_2,\dots,a_n$。

【输出格式】

输出到 $\texttt{draw.out}$ 中。

一行一个整数，表示不同的涂色方案数对 $998244353$ 取模后的结果。

【样例 1 输入】

5 4
1 2 3 4 5

【样例 1 输出】

56

【样例 2 输入】

5 3
1 1 1 1 1

【样例 2 输出】

11

【数据范围】

对于所有测试数据：$1\le k< n\le 300$，$1\le a_i<998244353$。