播放列表

题目描述

高桥君的播放列表中有 $N$ 首歌曲。 第 $i$ 首歌曲 $(1 \leq i \leq N)$ 的长度为 $T_i$ 秒。

高桥君在时刻 $0$ 开始播放列表的随机播放。

随机播放重复以下操作：从 $N$ 首歌曲中等概率地选择一首，并将其完整播放。 这里，歌曲是连续播放的：一首歌曲结束后，立即开始播放下一首被选中的歌曲。 连续选择同一首歌也是允许的。

求时刻 $0$ 之后 $(X + 0.5)$ 秒时正在播放歌曲 $1$ 的概率，对 $998244353$ 取模。

概率对 $998244353$ 取模的方法

可以证明，本题所求概率始终是有理数。 并且，本题的约束保证：当所求概率表示为既约分数 $\frac{y}{x}$ 时，$x$ 不被 $998244353$ 整除。

此时，存在唯一一个 $0$ 到 $998244352$ 之间（含端点）的整数 $z$，使得 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入格式

输入按以下格式从标准输入给出：

$N$ $X$
$T_1$ $T_2$ $\ldots$ $T_N$

输出格式

输出时刻 $0$ 之后 $(X+0.5)$ 秒时正在播放第一首歌的概率，对 $998244353$ 取模。

样例

3 6
3 5 6

369720131

如果歌曲按以下几种顺序播放，则在时刻 $0$ 之后 $6.5$ 秒时正在播放歌曲 $1$。

歌曲 $1$ $\to$ 歌曲 $1$ $\to$ 歌曲 $1$

歌曲 $2$ $\to$ 歌曲 $1$

歌曲 $3$ $\to$ 歌曲 $1$

这些情况之一发生的概率为 $\frac{7}{27}$。

因为 $369720131\times 27\equiv 7 \pmod{998244353}$，所以应输出 $369720131$。

5 0
1 2 1 2 1

598946612

时刻 $0$ 之后 $0.5$ 秒时，第一首被播放的歌曲仍在播放，因此所求概率为 $\frac{1}{5}$。

注意不同的歌曲长度可能相同。

5 10000
1 2 3 4 5

586965467

数据范围

• $2 \leq N\leq 10^3$
• $0 \leq X\leq 10^4$
• $1 \leq T_i\leq 10^4$
• 输入中的所有数值均为整数。