U511771 wp1 - wyz loves her


小w喜欢想她（即在群里发电）。在每一单位时间内，他会连续想她多次。具体地，在第 $i$ 个单位时间，他会重复执行一下操作： + 有 $p_i$ 的概率想她一次，继续此操作； + 有 $1-p_i$ 的概率在这个时间单位内不再想她。 由于发电多了群友们会觉得小w很烦，于是他们想让你求出在 $n$ 个单位时间内小w想她次数小于等于 $k$ 的概率来决定要不要把小w踢出群。 注意，每天的 $p_i$ 不一定都相等。 由于存在浮点误差，且答案可能很大，输入的 $p_i$ 是真实概率对 $998244353$ 取模的结果，并且你只需输出答案对 $998244353$ 取模后的结果。

一行两个正整数 $n$，$k$。 接下来一行，$n$ 个自然数 $p_i$，表示每天的概率对 $998244353$ 取模的结果。

一行一个自然数，表示答案对 $998244353$ 取模的结果。

## 样例解释 对于第一组样例，$p_1=\frac{1}{2}$，小w在第一个单位时间想她 $0$ 次的概率为 $1-p_1=\frac{1}{2}$，$1$ 次的概率为 $p_1(1-p_1)=\frac{1}{4}$，$2$ 次的概率为 $p_1^2(1-p_i)=\frac{1}{8}$，故答案为 $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}=\frac{7}{8}$。 对于第二组样例，$p_1=\frac{1}{3}$，小w在第一个单位时间想她 $0$ 次的概率为 $\frac{1}{3}$，$1$ 次的概率为 $\frac{1}{9}$，$2$ 次的概率为 $\frac{1}{27}$；$p_2=\frac{1}{3}$，小w在第二个单位时间想她 $0$ 次的概率为 $\frac{2}{3}$，$1$ 次的概率为 $\frac{4}{9}$，$2$ 次的概率为 $\frac{8}{27}$。故答案为 $(\frac{1}{3}\times\frac{2}{3})+(\frac{1}{9}\times\frac{2}{3}+\frac{1}{3}\times\frac{4}{9})+(\frac{1}{27}\times\frac{2}{3}+\frac{1}{9}\times\frac{4}{9}+\frac{1}{3}\times\frac{8}{27})=\frac{50}{81}$。 ## 子任务 | Subtask | $n\le$ | $k\le$ | 特殊性质 | 分数 | |:-:|:-:|:-:|:-:|:-:| | $1$ | $10$ | $10$ | - | $10$ | | $2$ | $500$ | $500$ | - | $10$ | | $3$ | $5000$ | $5000$ | - | $20$ | | $4$ | $10^5$ | $10^5$ | $A$ | $10$ | | $5$ | $10^5$ | $10^5$ | $B$ | $20$ | | $6$ | $10^5$ | $10^5$ | - | $20$ | | $7$ | $2\times10^5$ | $2\times10^5$ | - | $10$ | 特殊性质 $A$：保证 $p_i\in\{0,1\}$ 且存在 $i$ 使得 $p_i=1$。 特殊性质 $B$：保证所有 $p_i$ 均相等。 对于所有数据，$1 \le n \le 2 \times 10^5$，$1 \le k \le 2 \times 10^5$，$0 \le p_i < 998244353$。 **注意：本题卡常，请对代码进行必要的常数优化。** **Subtask 1-6 时限为 1s，Subtask 7 时限为 600ms。**