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 翻译