题目描述

Given are a sequence of $N$ positive integers $A_1$, $A_2$, $\ldots$, $A_N$ and another positive integer $S$.
For a non-empty subset $T$ of the set $\{1, 2, \ldots , N \}$, let us define $f(T)$ as follows:

• $f(T)$ is the number of different non-empty subsets $\{x_1, x_2, \ldots , x_k \}$ of $T$ such that $A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S$.

Find the sum of $f(T)$ over all $2^N-1$ subsets $T$ of $\{1, 2, \ldots , N \}$. Since the sum can be enormous, print it mod $998244353$.

给出一个由 $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$ 的个数。
• 求 $\{1, 2, \ldots , N \}$ 的所有 $2^N-1$ 子集 $T$ 中 $f(T)$ 的和。由于和可能很大，请打印出它的模数 $998244353$ 。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印 $f(T)$ mod $998244353$ 的和。

样例 #1

样例输入 #1

3 4
2 2 4

样例输出 #1

6

样例 #2

样例输入 #2

5 8
9 9 9 9 9

样例输出 #2

0

样例 #3

样例输入 #3

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

样例输出 #3

3296

说明

数据规模与约定

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

样例 $1$ 解释

每个 $T$ 的 $f(T)$ 值如下所示。这些值的总和为 $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\}$ )