所有子集的背包

题目描述

给定长度为 $N$ 的正整数序列 $A_1$, $A_2$, $\ldots$, $A_N$ 和正整数 $S$。

对于集合 $\{1, 2, \ldots , N \}$ 的非空子集 $T$,按如下方式定义 $f(T)$:

• $T$ 的满足 $A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S$ 的非空子集 $\{x_1, x_2, \ldots , x_k \}$ 的个数

作为 $T$ 可取的集合共有 $2^N-1$ 种,请计算所有这些集合对应的 $f(T)$ 之和。但是,由于答案可能非常大,请输出除以 $998244353$ 的余数。

输入格式

输入按以下格式从标准输入给出:

$N$ $S$
$A_1$ $A_2$ $...$ $A_N$

输出格式

输出 $f(T)$ 之和除以 $998244353$ 的余数。

样例

3 4
2 2 4

6

可以分别计算如下,其和为 $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$ 个)

5 8
9 9 9 9 9

0

10 10
3 1 4 1 5 9 2 6 5 3

3296

数据范围

• 输入均为整数。
• $1 \leq N \leq 3000$
• $1 \leq S \leq 3000$
• $1 \leq A_i \leq 3000$