题目描述

给定 $N$ 个正整数 $A_1, A_2, \\ldots, A_N$，以及另一个正整数 $S$。对于集合 $\\{1, 2, \\ldots , N \\}$ 的非空子集 $T$，定义 $f(T)$ 如下：

• $f(T)$ 是满足 $A_{x_1}+A_{x_2}+\\cdots +A_{x_k} = S$ 的 $T$ 的不同非空子集 $\\{x_1, x_2, \\ldots , x_k \\}$ 的数量。

找出所有 $2^N-1$ 个 $\\{1, 2, \\ldots , N \\}$ 的子集 $T$ 上的 $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

对于每个 $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\\}$）

示例输入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