题目描述

長さ $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$ で割ったあまりを出力せよ。

题目大意

已知包含 $N$ 个整数的序列 $A$，和一个整数 $S$。集合 $T$ 是 $\{1,2,3,\cdots,N\}$ 的非空子集。

定义函数 $f(T)$ 为：
满足 ${x_1, x_2, \ldots , x_k }\in T$ 且 $A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S$ 的方案数。

求出所有的 $f(T)$ 之和。结果模 $998244353$。

Translated by

3 4
2 2 4

6

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$

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$ つ)