AT_abc169_f [ABC169F] Knapsack for All Subsets

[problemUrl]: https://atcoder.jp/contests/abc169/tasks/abc169_f 長さ $ N $ の正整数列 $ A_1 $, $ A_2 $, $ \ldots $, $ A_N $ と正の整数 $ S $ が与えられます。 集合$ \{1,\ 2,\ \ldots\ ,\ N\ \} $ の空でない部分集合 $ T $ について、$ f(T) $ を以下のように定めます。 - $ T $ の空でない部分集合 $ \{x_1,\ x_2,\ \ldots\ ,\ x_k\ \} $ であって、 $ A_{x_1}+A_{x_2}+\cdots\ +A_{x_k}\ =\ S $ をみたすものの個数 $ T $ として考えられる集合は $ 2^N-1 $ 通りありますが、そのすべてに対する $ f(T) $ の和を求めてください。ただし、答えは非常に大きくなることがあるので、$ 998244353 $ で割ったあまりを出力してください。

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

$ f(T) $ の和を $ 998244353 $ で割ったあまりを出力せよ。

### 制約 - 入力は全て整数である。 - $ 1\ \leq\ N\ \leq\ 3000 $ - $ 1\ \leq\ S\ \leq\ 3000 $ - $ 1\ \leq\ A_i\ \leq\ 3000 $ ### Sample Explanation 1 それぞれ以下のように計算できて、その和は $ 6 $ です。 - $ f(\{1\})\ =\ 0 $ - $ f(\{2\})\ =\ 0 $ - $ f(\{3\})\ =\ 1 $ ( $ \{3\} $ の $ 1 $ つ) - $ f(\{1,\ 2\})\ =\ 1 $ ( $ \{1,\ 2\} $ の $ 1 $ つ) - $ f(\{2,\ 3\})\ =\ 1 $ ( $ \{3\} $ の $ 1 $ つ) - $ f(\{1,\ 3\})\ =\ 1 $ ( $ \{3\} $ の $ 1 $ つ) - $ f(\{1,\ 2,\ 3\})\ =\ 2 $ ( $ \{1,\ 2\},\ \{3\} $ の $ 2 $ つ)