Bob 喜欢抽卡。

Bob 最近入坑了一款叫“主公连结” 的抽卡游戏。游戏中共有 $n$ 个不同的角色，编号为 $1\sim n$。当 Bob 获得其中的编号连续的 $k$ 张卡时，就可以组出理论最强阵容。

当期卡池中共有 $m$ 张不同的卡，每次抽卡，Bob 都可以等概率随机获得一张卡池中的卡。如果 Bob 抽到了一张他已经拥有的卡，那么什么事都不会发生，等于 Bob 浪费了这次抽卡机会。Bob 是个谨慎的人，他想知道，如果他不停地抽卡直到抽到编号连续的 $k$ 张卡时停止抽卡，期望需要抽多少轮。

输入格式

第一行输入两个整数 $m,k$。

第二行输入 $m$ 个两两不同的整数 $a_1,a_2,\dots ,a_m$，表示卡池中有哪些角色。

题面中的 $n$ 即为最大的 $a_i$ 的值。

输出格式

输出一行一个整数，代表期望轮数对 $p=998244353$ 取模后的结果。即，如果期望数量的最简分数表示为 $\frac{a}{b}$，你需要输出一个整数 $c$ 满足 $c\times b\equiv a(\mathrm{mod}p)$。

样例一

input

3 2
1 2 3

output

499122180

explanation

如果第一轮抽到的是 $2$ 号卡，那么期望需要抽 $1+\frac{3}{2}$ 轮；如果第一轮抽到的是 $1$ 号卡或 $3$ 号卡，那么期望需要抽 $1+3$ 轮。故答案为 $\frac{1}{3}(1+\frac{3}{2})+\frac{2}{3}(1+3)=3.5$。

样例二

input

10 2
1 2 3 4 5 7 8 9 11 12

output

839792873

限制与约定

对于前 $10\mathrm{\%}$ 的数据，$m\le 10$。

对于另外 $10\mathrm{\%}$ 的数据，$m\le 500$ 且 $k=m-1$。

对于另外 $10\mathrm{\%}$ 的数据，$m\le 500$ 且保证有且仅有一组理论最强阵容。

对于另外 $10\mathrm{\%}$ 的数据，$m\le 500$ 且保证任意两组可抽出的理论最强阵容不交。

对于前 $50\mathrm{\%}$ 的数据，$m\le 500$。

对于前 $70\mathrm{\%}$ 的数据，$m\le 5000$。

对于另外 $10\mathrm{\%}$ 的数据，$k=5$。

对于另外 $10\mathrm{\%}$ 的数据，$k=2000$。

对于 $100\mathrm{\%}$ 的数据，$1\le m\le 200000,1\le a_i\le 2m,2\le k\le m$，保证卡池中至少存在一组可抽出的理论最强阵容（即编号连续的 $k$ 张卡）。

时间限制：$5\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载