AT_abc169_f [ABC169F] Knapsack for All Subsets

给定一个长度为 $N$ 的正整数序列 $A_1, A_2, \ldots, A_N$ 和一个正整数 $S$。 对于集合 $\{1, 2, \ldots, N\}$ 的所有非空子集 $T$，定义 $f(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$ 种，请计算所有 $T$ 的 $f(T)$ 之和。由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入以以下格式从标准输入给出。 > $N$ $S$ $A_1$ $A_2$ $\ldots$ $A_N$

请输出所有 $T$ 的 $f(T)$ 之和对 $998244353$ 取模的结果。

### 限制条件 - 输入均为整数。 - $1 \leq N \leq 3000$ - $1 \leq S \leq 3000$ - $1 \leq A_i \leq 3000$ ### 样例解释 1 可以分别计算如下，和为 $6$。 - $f(\{1\}) = 0$ - $f(\{2\}) = 0$ - $f(\{3\}) = 1$（$\{3\}$ 这一个子集） - $f(\{1, 2\}) = 1$（$\{1, 2\}$ 这一个子集） - $f(\{2, 3\}) = 1$（$\{3\}$ 这一个子集） - $f(\{1, 3\}) = 1$（$\{3\}$ 这一个子集） - $f(\{1, 2, 3\}) = 2$（$\{1, 2\}$、$\{3\}$ 这两个子集） 由 ChatGPT 4.1 翻译