AT_abc323_e [ABC323E] Playlist

[problemUrl]: https://atcoder.jp/contests/abc323/tasks/abc323_e 高橋君は $ N $ 曲からなるプレイリストを持っています。 曲 $ i $ $ (1\ \leq\ i\ \leq\ N) $ の長さは $ T_i $ 秒です。 高橋君は時刻 $ 0 $ にプレイリストのランダム再生を開始しました。 ランダム再生では、$ N $ 曲の中から等確率で $ 1 $ つを選びその曲を最後まで再生することが繰り返されます。 ここで、曲の再生は休みなく行われ、$ 1 $ つの曲が終わったらすぐに次に選ばれた曲が始まります。 また、同じ曲が連続して選ばれる事もあります。 時刻 $ 0 $ から $ (X+0.5) $ 秒後に曲 $ 1 $ が再生されている確率を $ \text{mod}998244353 $ で求めてください。 確率 $ \text{mod\ }\ 998244353 $ の定義この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 $ \frac{y}{x} $ で表したときに $ x $ が $ 998244353 $ で割り切れないことが保証されます。 このとき $ xz\ \equiv\ y\ \pmod{998244353} $ を満たすような $ 0 $ 以上 $ 998244352 $ 以下の整数 $ z $ が一意に定まります。この $ z $ を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ T_1 $ $ T_2 $ $ \ldots $ $ T_N $

時刻 $ 0 $ から $ (X+0.5) $ 秒後にプレイリストの $ 1 $ 番目の曲が再生されている確率を $ \text{mod}998244353 $ で出力せよ。

### 制約 - $ 2\ \leq\ N\leq\ 10^3 $ - $ 0\ \leq\ X\leq\ 10^4 $ - $ 1\ \leq\ T_i\leq\ 10^4 $ - 入力はすべて整数 ### Sample Explanation 1 時刻 $ 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 $ を出力します。 ### Sample Explanation 2 時刻 $ 0 $ から $ 0.5 $ 秒後には最初に再生された曲が再生されているため、求める確率は $ \frac{1}{5} $ となります。 同じ長さの異なる曲が存在することがあることに注意してください。