题目描述

赵喜娜有一个音乐播放器（赛后回家看）。

他的音乐播放器里面一共有$n$首歌，赵喜娜对第$i$首歌的喜爱程度是$a_i$。

赵喜娜今天选择了随机播放模式，具体地：

他的播放器会随机播放一首歌，等这首歌结束后，会继续随机播放下一首歌（不排除这首歌跟刚那首歌一样的可能性）。

当赵喜娜首次听到第$i$首歌的时候，他的愉悦程度会增加$a_i$，第二次及以后听到，则没有反应了。

当赵喜娜听完某首歌后，总的愉悦程度$\geq S$，赵喜娜就会开心的关掉播放器，完成今天的听歌。

问：赵喜娜听到的最后一首歌是第$i$首歌的概率是多少？

可以证明结果一定可以被化简为一个分数$\frac{x}{y}$，你需要输出$x/y \mod 998244353$。

提示：解此题的时候也许你可能不得不在$\ mod \ p$意义下除以一个数字（此处$p$是质数），那么你就需要逆元这个东西。

如果你不会逆元的话，简单介绍一下逆元：

假设你现在需要求$x/y\mod \ p$的结果，比如$3*5/3\mod 7$，如果你直接每步$mod\ 7$计算的话，答案是$(3*5\%7)/3 \% 7=0$。但实际上结果显然是$5$。

所以你需要更高级的东西，费马小定理：假设有质数$p$以及非负整数$a<p$，那么$a^{p-1}\%p=1$。也就是说，$a^{p-1}$实际上就是$\mod\ p$意义下的数字$1$。

那么$x/y\mod p$就可以写成$x\times y^{p-1}/y\mod p$。反正乘以$1$等于没乘对吧。

也就是说，我们如果要$/y$的话，可以当成要乘以$y^{p-2}$。

$y^{p-2}$就是$y$在$\mod p$意义下的逆元。

输入格式

第一行输入$n,S$。

接下来一行输入$n$个正整数表示$a_i$。

输出格式

$n$个数字表示答案。

样例输入 #1

4 3
1 2 3 4

样例输出 #1

582309206 582309206 915057324 915057324

样例解释 #1

想要以$2$结尾或者以$1$结尾，赵喜娜必须只听到歌$1$和歌$2$。

那么听歌序列只能是$111112$或者是$222221$这样。

$12$的概率是$\frac{1}{4}^2$。

$112$的概率是$\frac{1}{4}^3$。

$1112$的概率是$\frac{1}{4}^4$。

...

所以最终以$2$结尾的概率是$\frac{\frac{1}{16}}{1-\frac{1}{4}}=\frac{1}{12}$。

以$1$结尾的概率同样是$\frac{1}{12}$。

$\frac{1}{12}$在$\mod p$意义下是$1\times 12^{p-2}=582309206$。

以$3$和$4$结尾的概率一样，都是$\frac{5}{12}$。

样例输入 #2

4 7
1 2 3 4

样例输出 #2

582309206 582309206 748683265 83187030

数据范围

对于15%的数据：$n\leq 8,S\leq 10$。

对于40%的数据：$n\leq 20,S\leq 100$。

对于60%的数据：$n\leq 20$。

对于另10%的数据：$a_i$只有两种取值。

对于85%的数据：$n\leq 100,S\leq 1000$。

对于100%的数据：$n\leq 100,S\leq 10000,1\leq a_i\leq S,\sum a_i \geq S$。