問題文

長さ $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$ で割ったあまりを出力してください。

制約

• 入力は全て整数である。
• $1 \\leq N \\leq 3000$
• $1 \\leq S \\leq 3000$
• $1 \\leq A_i \\leq 3000$

入力

入力は以下の形式で標準入力から与えられる。

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

出力

$f(T)$ の和を $998244353$ で割ったあまりを出力せよ。

入力例 1

3 4
2 2 4

出力例 1

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

入力例 2

5 8
9 9 9 9 9

出力例 2

0

入力例 3

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

出力例 3

3296