AT_abc370_e [ABC370E] Avoid K Partition

[problemUrl]: https://atcoder.jp/contests/abc370/tasks/abc370_e 長さ $ N $ の数列 $ A\ =\ (A_1,\ A_2,\ \dots,\ A_N) $ および整数 $ K $ があります。 $ A $ をいくつかの連続部分列に分割する方法は $ 2^{N-1} $ 通りありますが、そのうち分割後に要素の和が $ K $ である列が存在しない分割の方法は何通りありますか。答えを $ 998244353 $ で割った余りを求めてください。 ここで、「$ A $ をいくつかの連続部分列に分割する」とは次の手順のことを言います。 - 分割後の数列の個数 $ k $ $ (1\ \leq\ k\ \leq\ N) $ および $ 1\ =\ i_1\ \lt\ i_2\ \lt\ \dots\ \lt\ i_k\ \lt\ i_{k+1}\ =\ N+1 $ を満たす整数列 $ (i_1,\ i_2,\ \dots,\ i_k,\ i_{k+1}) $ を自由に選ぶ。 - $ 1\ \leq\ n\ \leq\ k $ について、$ n $ 番目の数列を、$ A $ の $ i_n $ 番目から $ i_{n+1}\ -\ 1 $ 番目までの要素を順番を保ったまま取り出して出来る数列とする。 $ A\ =\ (1,\ 2,\ 3,\ 4,\ 5) $ のときの分割の例を以下に挙げます。 - $ (1,\ 2,\ 3),\ (4),\ (5) $ - $ (1,\ 2),\ (3,\ 4,\ 5) $ - $ (1,\ 2,\ 3,\ 4,\ 5) $

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ -10^{15}\ \leq\ K\ \leq\ 10^{15} $ - $ -10^9\ \leq\ A_i\ \leq\ 10^9 $ - 入力される値は全て整数 ### Sample Explanation 1 問題文の条件を満たす分割は次の $ 2 $ 通りです。 - $ (1),\ (2,\ 3) $ - $ (1,\ 2,\ 3) $