AtCoder Beginner Contest 169 - Knapsack for All Subsets

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 modulo 998244353.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 3000
 - 1 \leq S \leq 3000
 - 1 \leq A_i \leq 3000

-----Input-----
Input is given from Standard Input in the following format:
N S
A_1 A_2 ... A_N

-----Output-----
Print the sum of f(T) modulo 998244353.

-----Sample Input-----
3 4
2 2 4

-----Sample Output-----
6

For each T, the value of f(T) is shown below. The sum of these values is 6.
 - f(\{1\}) = 0
 - f(\{2\}) = 0
 - f(\{3\}) = 1 (One subset \{3\} satisfies the condition.)
 - f(\{1, 2\}) = 1 (\{1, 2\})
 - f(\{2, 3\}) = 1 (\{3\})
 - f(\{1, 3\}) = 1 (\{3\})
 - f(\{1, 2, 3\}) = 2 (\{1, 2\}, \{3\})

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
import numpy as np
(n, s) = list(map(int, input().split()))
a = [int(i) for i in input().split()]
mod = 998244353
dp = np.zeros(s + 1, dtype='i8')
dp[0] = 1
for aa in a:
	tmp = 2 * dp % mod
	tmp[aa:] += dp[:-aa]
	tmp %= mod
	dp = tmp
print(dp[s])


(n, s) = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0] * (s + 1) for i in range(n + 1)]
dp[0][0] = 1
mod = 998244353
ans = 0
for i in range(n):
	for j in range(s + 1):
		if j + a[i] <= s:
			dp[i + 1][j + a[i]] += dp[i][j]
		dp[i + 1][j] += dp[i][j] * 2
		dp[i + 1][j] %= mod
print(dp[n][s])


(n, s) = map(int, input().split())
a = list(map(int, input().split()))
import numpy as np
mod = 998244353
f = np.zeros(3020, np.int64)
f[0] = 1
for b in a:
	ff = 2 * f
	ff[b:] += f[:-b]
	ff %= mod
	f = ff
print(f[s])


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for j in range(S + 1):
		dp[i + 1][j] += 2 * dp[i][j]
		dp[i + 1][j] %= mod
		if j + A[i] <= S:
			dp[i + 1][j + A[i]] += dp[i][j]
			dp[i + 1][j + A[i]] %= mod
print(dp[N][S])


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
DP = [[0] * (S + 1) for i in range(N + 1)]
DP[0][0] = 1
for i in range(N):
	for j in range(S + 1):
		if j >= A[i]:
			DP[i + 1][j] = (DP[i][j] * 2 + DP[i][j - A[i]]) % MOD
		else:
			DP[i + 1][j] = DP[i][j] * 2 % MOD
print(DP[-1][-1] % MOD)


(N, S) = map(int, input().split())
A = [int(i) for i in input().split()]
mod = 998244353
dp = [0] * (S + 1)
dp[0] = 1
for a in A:
	for i in range(S, -1, -1):
		if i >= a:
			dp[i] = dp[i] * 2 + dp[i - a]
		else:
			dp[i] = dp[i] * 2
		dp[i] %= mod
print(dp[-1])


import numpy as np

def main():
	(n, s) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	dp = np.array([0 for i in range(s + 1)])
	dp[0] = 1
	for ai in A:
		tmp = dp[:-ai].copy()
		dp *= 2
		dp[ai:] += tmp
		dp %= 998244353
	print(dp[s])

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10000000)
MOD = 998244353
INF = 10 ** 15

def main():
	(N, S) = map(int, input().split())
	A = list(map(int, input().split()))
	dp = [0] * (1 + S)
	dp[0] = pow(2, N, MOD)
	inv2 = pow(2, MOD - 2, MOD)
	for a in A:
		for s in range(S, a - 1, -1):
			dp[s] = (dp[s] + dp[s - a] * inv2) % MOD
	print(dp[S])

def __starting_point():
	main()
__starting_point()


import numpy as np
import numba
from typing import List

@numba.jit
def solver(N: int, S: int, A: np.array) -> int:
	dp = np.zeros((N + 1, S + 1), dtype=np.int64)
	dp[0, 0] = 1
	MOD = 998244353
	for i in range(N):
		for j in range(S + 1):
			dp[i + 1, j] += 2 * dp[i, j]
			dp[i + 1, j] %= MOD
			if j + A[i] <= S:
				dp[i + 1, j + A[i]] += dp[i, j]
				dp[i + 1, j + A[i]] %= MOD
	return dp[N, S]

def main():
	(N, S) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	ans = solver(N, S, np.array(A))
	print(ans)

def __starting_point():
	import sys
	sys.setrecursionlimit(10000)
	main()
__starting_point()


MOD = 998244353
(n, s) = map(int, input().split())
nums = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for j in range(s + 1):
		dp[i + 1][j] += dp[i][j] * 2 % MOD
		if j >= nums[i]:
			dp[i + 1][j] += dp[i][j - nums[i]]
		dp[i + 1][j] %= MOD
print(dp[n][s])


import numpy as np
mod = 998244353
(n, s) = map(int, input().split())
dp = np.zeros(s + 1, dtype=int)
dp[0] = 1
for a in map(int, input().split()):
	pre_dp = dp
	dp = pre_dp * 2 % mod
	dp[a:] = (dp[a:] + pre_dp[:-a]) % mod
print(dp[-1])


(N, S) = map(int, input().split())
A = [0] + list(map(int, input().split()))
H = [[0] * (S + 1) for i in range(N + 1)]
M = 998244353
for x in range(N + 1):
	H[x][0] = 1
for x in range(1, N + 1):
	for s in range(S + 1):
		if s >= A[x]:
			H[x][s] = (2 * H[x - 1][s] + H[x - 1][s - A[x]]) % M
		else:
			H[x][s] = 2 * H[x - 1][s] % M
print(H[-1][-1])


MOD = 998244353
(n, s) = map(int, input().split())
A = map(int, input().split())
dp = [0] * (s + 1)
dp[0] = 1
inv_2 = (MOD + 1) // 2
for a in A:
	for j in reversed(range(s + 1)):
		if j - a < 0:
			continue
		dp[j] += dp[j - a] * inv_2
		dp[j] %= MOD
print(dp[-1] * pow(2, n, MOD) % MOD)


import sys
import numpy as np
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
MOD = 998244353
(N, S) = lr()
A = lr()
dp = np.zeros(S + 1, np.int64)
dp[0] = 1
for a in A:
	prev = dp.copy()
	dp[a:] += dp[:-a]
	dp += prev
	dp %= MOD
answer = dp[S]
print(answer % MOD)


import numpy as np
(N, S) = list(map(int, input().split()))
A = np.array(list(map(int, input().split())))
P = 998244353
table = np.zeros((N, S + 1), dtype=int)
table[0, 0] = 2
if A[0] <= S:
	table[0, A[0]] = 1
for i in range(1, N):
	Ai = A[i]
	table[i] += 2 * table[i - 1]
	if Ai <= S:
		table[i][Ai:] += table[i - 1][:S - Ai + 1]
	table[i] = table[i] % P
print(table[N - 1][S])


(n, s, *a) = map(int, open(0).read().split())
mod = 998244353
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = pow(2, n, mod)
for i in range(n):
	for j in range(s + 1):
		dp[i + 1][j] += dp[i][j]
		dp[i + 1][j] %= mod
		if j + a[i] <= s:
			dp[i + 1][j + a[i]] += dp[i][j] * (mod + 1) // 2
			dp[i + 1][j + a[i]] %= mod
print(dp[n][s])


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
L = [0 for _ in range(S + 1)]
L[0] = 1
F = {0}
for i in range(N):
	X = [[i, L[i]] for i in F]
	for j in F:
		L[j] *= 2
		L[j] %= mod
	for j in X:
		if A[i] + j[0] <= S:
			L[A[i] + j[0]] += j[1]
			L[A[i] + j[0]] %= mod
			F.add(A[i] + j[0])
print(L[S])


mod = 998244353
inv = pow(2, mod - 2, mod)
(n, s) = map(int, input().split())
a = list(map(int, input().split()))
dp = [0] * (s + 1)
dp[0] = pow(2, n, mod)
for i in a:
	for j in range(s, i - 1, -1):
		dp[j] = (dp[j] + dp[j - i] * inv) % mod
print(dp[s])


(N, S) = map(int, input().split())
As = list(map(int, input().split()))
P = 998244353
memo = [[0 for _ in range(N + 1)] for _ in range(S + 1)]
for i in range(N + 1):
	memo[0][i] = 2 ** i % P
for (i, a) in enumerate(As):
	for j in range(S + 1):
		if j - a < 0:
			memo[j][i + 1] = memo[j][i] * 2 % P
		else:
			memo[j][i + 1] = (memo[j][i] * 2 + memo[j - a][i]) % P
print(memo[S][N])


(n, s) = map(int, input().split())
a = [int(j) for j in input().split()]
dp = [0] * (3000 + 1)
dp[0] = 1
import numpy as np
pre = np.array(dp)
mod = 998244353
for i in a:
	dp = pre * 2
	dp[i:] += pre[:-i]
	dp %= mod
	pre = dp
print(dp[s])


import numpy as np
mod = 998244353
(n, s) = list(map(int, input().split()))
A = list(map(int, input().split()))
DP = np.zeros(3005, dtype=np.int64)
DP[0] = 1
for a in A:
	double = DP * 2
	shift = np.hstack([np.zeros(a), DP[:-a]]).astype(np.int64)
	DP = double + shift
	DP %= mod
print(DP[s])


(N, S) = map(int, input().split())
As = list(map(int, input().split()))
mod = 998244353
dp = [[0] * (S + 1) for i in range(N + 1)]
dp[0][0] = 1
for i in range(1, N + 1):
	a = As[i - 1]
	for s in range(S + 1):
		if s - a >= 0:
			dp[i][s] += dp[i - 1][s - a] + dp[i - 1][s] * 2
		else:
			dp[i][s] += dp[i - 1][s] * 2
		dp[i][s] %= mod
print(dp[-1][-1] % mod)


import numpy as np
(N, S) = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
mod = 998244353
coef = np.zeros(3001, dtype=int)
coef[0] = 1
for a in A:
	coef2 = coef[:-a].copy()
	coef *= 2
	coef[a:] += coef2
	coef %= mod
print(coef[S])


(n, s) = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
a = 499122177
b = pow(2, n - 1, mod)
dp = [[0] * (s + 1) for i in range(n + 1)]
for i in range(n + 1):
	dp[0][0] = pow(2, n, mod)
for i in range(1, n + 1):
	dp[i] = dp[i - 1][0:s + 1]
	for j in range(s + 1):
		if j + A[i - 1] > s:
			break
		dp[i][j + A[i - 1]] = (dp[i - 1][j + A[i - 1]] + dp[i - 1][j] * a) % mod
print(dp[-1][-1])


import numpy as np
MOD = 998244353

def main():
	(n, s) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	dp = np.zeros((n + 1, s + 1), dtype=np.int64)
	dp[0][0] = 1
	for (i, v) in enumerate(a):
		dp[i + 1] += dp[i] * 2
		if v <= s:
			dp[i + 1][v:] += dp[i][:-v]
		dp[i + 1] %= MOD
	print(int(dp[n][s]) % MOD)

def __starting_point():
	main()
__starting_point()


import numpy as np
import sys
input = sys.stdin.readline

def main():
	(n, s) = map(int, input().split())
	A = [int(i) for i in input().split()]
	MOD = 998244353
	dp = np.zeros(s + 1, dtype='int32')
	dp[0] = 1
	for a in A:
		p = dp * 2 % MOD
		p %= MOD
		p[a:] += dp[:-a]
		dp = p % MOD
	print(dp[s])

def __starting_point():
	main()
__starting_point()


(n, s) = map(int, input().split())
a = list(map(int, input().split()))
d = [[0] * (s + 1) for _ in range(n + 1)]
d[0][0] = 1
for j in range(0, s + 1):
	for i in range(1, n + 1):
		d[i][j] = 2 * d[i - 1][j]
		if a[i - 1] <= j:
			d[i][j] += d[i - 1][j - a[i - 1]]
		d[i][j] = d[i][j] % 998244353
print(d[n][s])


mod = 998244353
(n, s) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
while a[-1] > s:
	a.pop(-1)
	if a == []:
		print(0)
		exit()
dp = [0] * (s + 1)
dp[0] = 1
for i in a:
	newdp = [2 * j % mod for j in dp]
	for j in range(s - i + 1):
		newdp[j + i] += dp[j]
	dp = newdp
print(dp[s] * pow(2, n - len(a), mod) % mod)


(n, s) = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353
half = mod // 2 + 1
now = [0 for _ in range(s + 1)]
dp00 = 1
for _ in range(n):
	dp00 *= 2
	dp00 %= mod
now[0] = dp00
for i in range(n):
	for j in range(s + 1)[::-1]:
		if j + a[i] <= s:
			now[j + a[i]] += now[j] * half
			now[j + a[i]] %= mod
print(now[-1] % mod)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list('abcdefghijklmnopqrstuvwxyz')
ALF = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
INF = float('inf')
import numpy as np
(N, S) = list(map(int, input().split()))
MOD = 998244353
A = list(map(int, input().split()))
dp = np.zeros(S + 1, dtype=np.int64)
dp[0] = 2
if A[0] <= S:
	dp[A[0]] = 1
for i in range(1, N):
	a = A[i]
	p = dp * 2
	if a <= S:
		p[a:] += dp[:-a]
	p %= MOD
	dp = p
print(dp[S])


import sys
import numpy as np

def input():
	return sys.stdin.readline().rstrip()

def main():
	(n, s) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	mod = 998244353
	dp = np.zeros(3001, dtype=np.int64)
	dp[0] = 1
	for AA in A:
		dp = dp * 2 + np.concatenate([np.zeros(AA, dtype=np.int64), dp[:3001 - AA]])
		dp %= mod
	print(dp[s])

def __starting_point():
	main()
__starting_point()


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
pr = 998244353

def gya(n):
	return pow(n, pr - 2, pr)
p = pow(2, N - 1, pr)
l = [0] * (S + 1)
g = gya(2)
for i in A:
	for j in range(S - i, -1, -1):
		l[i + j] = (l[i + j] + l[j] * g) % pr
	if i <= S:
		l[i] += p
print(l[-1])


mod = 998244353
(n, s) = map(int, input().split())
A = list(map(int, input().split()))
div2 = pow(2, mod - 2, mod)
dp = [0] * (s + 1)
dp[0] = pow(2, n, mod)
for a in A:
	newdp = [0] * (s + 1)
	for i in range(s, a - 1, -1):
		before = i - a
		newdp[i] += dp[before] * div2 % mod
		newdp[i] %= mod
	for i in range(s + 1):
		newdp[i] += dp[i]
		newdp[i] %= mod
	dp = newdp
print(dp[-1])


import numpy as np

def main():
	MOD = 998244353
	(N, S) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	dp = np.zeros(S + 1, np.int64)
	dp[0] = 1
	for (i, a) in enumerate(A, start=1):
		dp_next = 2 * dp
		dp_next[a:] += dp[:-a]
		dp_next %= MOD
		dp = dp_next
	print(dp[S])

def __starting_point():
	main()
__starting_point()


def f_knapsack_for_all_subsets_power_series(MOD=998244353, MAX=3010):
	import numpy as np
	(N, S) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	f = np.zeros(MAX + 1, np.int64)
	f[0] = 1
	for a in A:
		f_next = 2 * f
		f_next[a:] += f[:-a]
		f_next %= MOD
		f = f_next
	return f[S]
print(f_knapsack_for_all_subsets_power_series())


def main():
	import sys
	sys.setrecursionlimit(10 ** 9)
	input = sys.stdin.readline
	import numpy as np
	(N, S) = map(int, input().split())
	A = list(map(int, input().split()))
	MOD = 998244353
	dp = np.zeros(S + 1, dtype='int32')
	dp[0] = 1
	for i in range(N):
		p = dp * 2 % MOD
		p[A[i]:] += dp[:-A[i]]
		dp = p % MOD
	print(dp[S])
main()


(N, S) = map(int, input().split())
MOD = 998244353
A = list(map(int, input().split()))
dp = [[0] * (S + 1) for i in range(N + 1)]
dp[0][0] = 1
for (i, a) in enumerate(A, 1):
	for s in range(S + 1):
		dp[i][s] = 2 * dp[i - 1][s]
		if a <= s:
			dp[i][s] += dp[i - 1][s - a]
		dp[i][s] %= MOD
print(dp[-1][-1])


import sys
input = sys.stdin.readline

def solve():
	MOD = 998244353
	inv2 = pow(2, MOD - 2, MOD)
	(N, S) = map(int, input().split())
	As = list(map(int, input().split()))
	dp = [0] * (S + 1)
	dp[0] = pow(2, N, MOD)
	for A in As:
		for k in reversed(range(S - A + 1)):
			dp[k + A] += dp[k] * inv2
			dp[k + A] %= MOD
	print(dp[-1])
solve()


(N, S, *A) = map(int, open(0).read().split())
mod = 998244353
dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for j in range(S + 1):
		dp[i + 1][j] += dp[i][j] * 2
		dp[i + 1][j] %= mod
		if j + A[i] <= S:
			dp[i + 1][j + A[i]] += dp[i][j]
			dp[i + 1][j + A[i]] %= mod
print(dp[-1][-1])


(n, s) = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353
dp = [0 for _ in range(s + 1)]
dp[0] = 1
for i in range(n):
	plus = [dp[j - a[i]] if j - a[i] >= 0 else 0 for j in range(s + 1)]
	for j in range(s + 1):
		dp[j] = (dp[j] * 2 + plus[j]) % mod
print(dp[s])


import numpy as np
(n, s) = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 998244353
dp = np.zeros(s + 1, np.int64)
dp[0] = 1
for e in a:
	pre = dp.copy()
	dp = 2 * pre
	dp[e:] += pre[:-e]
	dp %= mod
ans = dp[s]
print(ans)


def main():
	mod = 998244353
	(n, s) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a = [i for i in a if i <= s]
	dp = [0 for i in range(s + 1)]
	half = pow(2, mod - 2, mod)
	for i in a:
		dp2 = [j for j in dp]
		dp2[i] = (dp2[i] + pow(2, n - 1, mod)) % mod
		for j in range(s - i + 1):
			dp2[j + i] = (dp2[j + i] + dp[j] * half) % mod
		dp = dp2
	print(dp[s])
main()


(n, s, *a) = map(int, open(0).read().split())
mod = 998244353
d = [0] * (s + 1)
d[0] = 1
for x in a:
	p = [0] * (s + 1)
	for i in range(s + 1):
		p[i] += d[i] * 2
		if i + x <= s:
			p[i + x] += d[i]
		p[i] %= mod
	d = p
print(d[-1])


import sys
input = sys.stdin.readline
import numpy as np
MOD = 998244353
(n, s) = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
dp = np.zeros(s + 1, dtype=np.int64)
dp[0] = 1
for a in A:
	t = dp.copy() * 2
	t[a:] += dp[:-a]
	t %= MOD
	dp = t
ans = dp[s]
print(ans)


import numpy as np
MOD = 998244353
(N, S) = list(map(int, input().split()))
A = list(map(int, input().split()))
coefs = np.array([0] * (S + 1))
coefs[0] = 1
for i in range(N):
	tmp = coefs[:]
	coefs = coefs * 2
	coefs[A[i]:] += tmp[:-A[i]]
	coefs %= MOD
print(coefs[-1])


import numpy as np
p = 998244353
(N, S) = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
dp = np.zeros(S + 1)
dp[0] = 1
for a in A:
	if S < a:
		dp *= 2
		dp %= p
		continue
	tmp = 2 * dp
	dp = np.append(np.zeros(a), dp[:S - a + 1])
	dp += tmp
	dp %= p
print(int(dp[S]))


(N, S) = map(int, input().split())
(*a,) = map(int, input().split())
mod = 998244353
dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for j in range(S + 1):
		dp[i + 1][j] = 2 * dp[i][j]
		if j >= a[i]:
			dp[i + 1][j] += dp[i][j - a[i]]
		dp[i + 1][j] %= mod
print(dp[N][S])


(N, S) = list(map(int, input().split()))
A = list(map(int, input().split()))

def f(N, S, A):
	MOD = 998244353
	dp = [0] * (S + 1)
	dp[0] = pow(2, N, MOD)
	div = pow(2, MOD - 2, MOD)
	m = 0
	for a in A:
		m += a
		for i in range(min(m, S), a - 1, -1):
			dp[i] = (dp[i] + dp[i - a] * div) % MOD
	return dp[S]
print(f(N, S, A))


import numpy as np
(N, S) = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 998244353
dp = np.zeros(S + 1)
dp[0] = 1
for i in range(N):
	tmp = dp * 2
	tmp[a[i]:] += dp[:-a[i]]
	dp = tmp % mod
print(int(dp[S]))


import numpy as np
MOD = 998244353
(n, s) = map(int, input().split())
a = list(map(int, input().split()))
fac_inv2 = pow(2, MOD - 2, MOD)
dp = np.zeros(s, 'int64')
for i in range(n):
	newdp = dp.copy()
	if a[i] < s:
		newdp[a[i]:] += dp[:s - a[i]] * fac_inv2 % MOD
	if a[i] <= s:
		newdp[a[i] - 1] += 1
	dp = newdp % MOD
ans = dp[-1]
ans *= pow(2, n - 1, MOD)
ans %= MOD
print(ans)


M = 998244353
(n, s, *l) = map(int, open(0).read().split())
dp = [[0] * (s + 1) for _ in '01']
dp[0][0] = 1
b = 0
for i in range(n):
	b ^= 1
	for j in range(s + 1):
		dp[b][j] = dp[b ^ 1][j] * 2
		if j >= l[i]:
			dp[b][j] += dp[b ^ 1][j - l[i]]
		dp[b][j] %= M
print(dp[n % 2][s])


import numpy as np
(n, s) = map(int, input().split())
a = list(map(int, input().split()))
dp = np.zeros(s + 1, dtype=np.int64)
mod = 998244353
dp[0] = 1
for i in range(n):
	p = dp * 2 % mod
	p[a[i]:] += dp[:-a[i]]
	dp = p % mod
print(dp[s])


import sys
sys.setrecursionlimit(10000000)
MOD = 998244353
INF = 10 ** 15
import numpy as np

def main():
	(N, S) = map(int, input().split())
	A = list(map(int, input().split()))
	dp = np.zeros(S + 1, np.int64)
	dp[0] = pow(2, N, MOD)
	inv2 = pow(2, MOD - 2, MOD)
	for a in A:
		dp[a:] = np.mod(dp[a:] + dp[:-a] * inv2, MOD)
	print(dp[S])

def __starting_point():
	main()
__starting_point()


MOD = 998244353
(N, S) = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0] * (S + 1)]
dp[0][0] = 1
for i in range(N):
	dp.append([d * 2 % MOD for d in dp[-1]])
	for k in range(A[i], S + 1):
		dp[-1][k] += dp[-2][k - A[i]]
print(dp[-1][-1] % MOD)


import numpy as np
MOD = 998244353
(N, S) = map(int, input().split())
As = list(map(int, input().split()))
dp = np.zeros((N + 1, S + 1), np.int64)
dp[0][0] = 1
for (n, A) in enumerate(As):
	dp[n + 1, :] = dp[n, :] * 2
	dp[n + 1, A:] += dp[n, :-A]
	dp[n + 1] %= MOD
print(dp[N, S])


(n, s) = map(int, input().split())
(*A,) = map(int, input().split())
mod = 998244353
dp = [[0] * (s + 1) for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for j in range(s + 1):
		if A[i] + j < s + 1:
			dp[i + 1][j + A[i]] += dp[i][j]
		dp[i + 1][j] += 2 * dp[i][j]
		dp[i + 1][j] %= mod
print(dp[-1][-1])


(n, s) = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
dp = [0 for _ in range(s + 1)]
dp[0] = 1
for v in a:
	for i in reversed(range(s - v + 1)):
		dp[i + v] += dp[i] * (MOD + 1) // 2
		dp[i + v] %= MOD
print(dp[s] * pow(2, n, MOD) % MOD)


dp = [[0] * 3001 for _ in range(3001)]
(n, s) = (int(num) for num in input().split())
a = [int(num) for num in input().split()]
MOD = 998244353
dp[0][0] = 1
for i in range(1, n + 1):
	for j in range(s + 1):
		dp[i][j] = dp[i - 1][j] * 2 % MOD
		if j >= a[i - 1]:
			dp[i][j] = (dp[i][j] + dp[i - 1][j - a[i - 1]]) % MOD
print(dp[n][s])


mod = 998244353
(N, S, *A) = map(int, open(0).read().split())
dp = [1] + [0] * S
for (i, a) in enumerate(A, 1):
	dp = [(2 * dp[j] + (dp[j - a] if j >= a else 0)) % mod for j in range(S + 1)]
print(dp[S])


(n, s) = map(int, input().split())
dp = [0] * (s + 1)
dp[0] = 1
ne = [0] * (s + 1)
mod = 998244353
for i in list(map(int, input().split())):
	for k in range(0, s + 1):
		if k + i <= s:
			ne[k + i] = (ne[k + i] + dp[k]) % mod
		ne[k] = (ne[k] + 2 * dp[k]) % mod
		dp[k] = 0
	(dp, ne) = (ne, dp)
print(dp[-1])


import math
import numpy as np
import queue
from collections import deque, defaultdict
import heapq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)

def main():
	(n, s) = list(map(int, ipt().split()))
	a = [int(i) for i in ipt().split()]
	mod = 998244353
	two = [1] * (n + 1)
	for i in range(n):
		two[i + 1] = two[i] * 2 % mod
	dp = np.zeros(3010, dtype=int)
	dp[0] = 1
	for (i, ai) in enumerate(a):
		ndp = dp * 2
		ndp[ai:] += dp[:-ai]
		ndp %= mod
		dp = ndp
	print(dp[s])
	return

def __starting_point():
	main()
__starting_point()


(n, s) = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
ans = 0
dp = [[0 for _ in range(s + 1)] for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for c in range(s + 1):
		if c >= A[i]:
			dp[i + 1][c] = (2 * dp[i][c] + dp[i][c - A[i]]) % mod
		else:
			dp[i + 1][c] = 2 * dp[i][c] % mod
print(dp[n][s] % mod)


(N, S) = map(int, input().split())
ls = list(map(int, input().split()))
MOD = 998244353
dp = [[1] + [0] * S for i in range(N + 1)]
for i in range(N):
	for j in range(S + 1):
		dp[i + 1][j] = dp[i][j] * 2 % MOD
		if ls[i] <= j:
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - ls[i]]) % MOD
print(dp[N][S])


MOD = 998244353
(n, s) = map(int, input().split())
As = list(map(int, input().split()))
dp = [0] * (s + 2)
dp[0] = 1
for a in As:
	for i in range(s + 1, -1, -1):
		if i - a < 0:
			continue
		dp[i] += dp[i - a] * (MOD + 1) // 2
		dp[i] %= MOD
print(dp[s] * pow(2, n, MOD) % MOD)


(n, s) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
mod = 998244353
dp = [0] * (s + 1)
dp[0] = 1
for i in a:
	dp2 = [0] * (s + 1)
	for j in range(s + 1):
		dp2[j] = dp[j] * 2
		if j >= i:
			dp2[j] += dp[j - i]
		dp2[j] %= mod
	dp = dp2
print(dp[-1])


mod = 998244353
(n, s) = map(int, input().split())
ar = list(map(int, input().split()))
dp = [0 for y in range(s + 1)]
dp[0] = 1
for i in range(n):
	for j in range(s, -1, -1):
		if j + ar[i] <= s:
			dp[j + ar[i]] = (dp[j] + dp[j + ar[i]]) % mod
		dp[j] = dp[j] * 2 % mod
print(dp[s])


(N, K) = map(int, input().split())
X = list(map(int, input().split()))
MOD = 998244353
dp = [[0] * (K + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	x = X[i]
	for j in range(K + 1):
		dp[i + 1][j] = 2 * dp[i][j]
		if j - x >= 0:
			dp[i + 1][j] += dp[i][j - x]
		dp[i + 1][j] %= MOD
print(dp[-1][-1])


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
dp = [[0 for _ in range(S + 1)] for __ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for j in range(S + 1):
		dp[i + 1][j] += 2 * dp[i][j]
		dp[i + 1][j] %= MOD
		if j + A[i] <= S:
			dp[i + 1][j + A[i]] += dp[i][j]
			dp[i + 1][j + A[i]] %= MOD
print(dp[N][S])


from collections import defaultdict
MOD = 998244353
(N, S) = map(int, input().split())
A = map(int, input().split())
dp = [0] * (S + 1)
dp[0] = 1
for a in A:
	ndp = [0] * (S + 1)
	for (total, cnt) in enumerate(dp):
		ndp[total] += dp[total] * 2 % MOD
		if total + a <= S:
			ndp[total + a] += dp[total]
			ndp[total + a] %= MOD
	dp = ndp
print(dp[-1] % MOD)


mod = 998244353
(n, s) = map(int, input().split())
arr = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
	val = arr[i - 1]
	for j in range(s, -1, -1):
		dp[i][j] = 2 * dp[i - 1][j]
		dp[i][j] %= mod
		if j - val >= 0 and dp[i - 1][j - val] != 0:
			dp[i][j] += dp[i - 1][j - val]
			dp[i][j] %= mod
print(dp[n][s])


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(1, N + 1):
	for s in range(S + 1):
		if s - A[i - 1] >= 0:
			dp[i][s] = (dp[i - 1][s] * 2 + dp[i - 1][s - A[i - 1]]) % MOD
		else:
			dp[i][s] = dp[i - 1][s] * 2 % MOD
print(dp[N][S])


MOD = 998244353
(n, s) = map(int, input().split())
a = list(map(int, input().split()))
f = [0] * (s + 1)
f[0] = pow(2, n, MOD)
v = pow(2, MOD - 2, MOD)
for x in a:
	for j in range(s, x - 1, -1):
		f[j] += f[j - x] * v
	for j in range(s + 1):
		f[j] %= MOD
print(f[s])


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
dp = [0] * (S + 1)
dp[0] = 1
for a in A:
	newDp = [d * 2 % MOD for d in dp]
	for s in range(S + 1):
		if s + a <= S:
			newDp[s + a] += dp[s]
	dp = newDp
print(dp[S] % MOD)


mod = 998244353
(n, s) = map(int, input().split())
a = list(map(int, input().split()))
table = [0] * (s + 1)
table[0] = 1
ans = 0
for ai in a:
	nxt = [0] * (s + 1)
	if ai <= s:
		for j in range(ai, s + 1):
			nxt[j] = table[j - ai]
	table = [(2 * table[i] + nxt[i]) % mod for i in range(s + 1)]
ans += table[-1]
ans %= mod
print(ans)


(n, s) = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1
for (i, a) in enumerate(A):
	for j in range(s + 1):
		dp[i + 1][j] += dp[i][j] * 2 % mod
		dp[i + 1][j] %= mod
		if j + a <= s:
			dp[i + 1][j + a] += dp[i][j]
			dp[i + 1][j + a] %= mod
print(dp[n][s] % mod)


(n, s) = map(int, input().split())
a = list(map(int, input().split()))
p = 998244353
data = [[0] * (s + 1) for i in range(n)]
gen = data[0]
gen[0] = 2
if a[0] <= s:
	gen[a[0]] += 1
for i in range(1, n):
	gen = data[i]
	mae = data[i - 1]
	for j in range(s + 1):
		gen[j] = mae[j] * 2
		if j - a[i] >= 0 and j - a[i] <= s:
			gen[j] += mae[j - a[i]]
		gen[j] %= p
print(data[-1][-1])


def resolve():
	(n, s) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	mod = 998244353
	modinv = pow(2, mod - 2, mod)
	dp = [0] * (s + 1)
	dp[0] = pow(2, n, mod)
	for i in a:
		for j in range(s - i, -1, -1):
			dp[j + i] += dp[j] * modinv
			dp[j + i] %= mod
	print(dp[-1])

def __starting_point():
	resolve()
__starting_point()


import numpy as np
(N, S) = map(int, input().split())
As = list(map(int, input().split()))
MOD = 998244353
d = np.zeros((3001, 3001))
d[0, 0] = 1
for i in range(1, N + 1):
	Ai = As[i - 1]
	d[i] += 2 * d[i - 1]
	d[i, Ai:] += d[i - 1][:-Ai]
	d[i] %= MOD
print(int(d[N][S]))


import sys
import numpy as np
input = lambda : sys.stdin.readline().rstrip()
MOD = 998244353
(N, S) = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = np.zeros(S + 1, np.int64)
dp[0] = 1
for a in A:
	f = 2 * dp
	f[a:] += dp[:-a]
	f %= MOD
	dp = f
print(dp[S])


import numpy as np
(N, S) = list(map(int, input().split()))
A = list(map(int, input().split()))
MOD = 998244353
dp = np.zeros(S + 1, dtype=int)
dp[0] = 1
for i in A:
	ep = dp.copy()
	ep += dp
	ep[i:] += dp[:-i]
	dp = ep % MOD
print(dp[S])


(n, s) = map(int, input().split())
a = list(map(int, input().split()))
t = [[0] * (s + 1) for i in range(n + 1)]
t[0][0] = 1
m = 998244353
for i in range(n):
	for j in range(s + 1):
		t[i + 1][j] = t[i][j] * 2
		if j >= a[i]:
			t[i + 1][j] += t[i][j - a[i]]
		t[i + 1][j] %= m
print(t[-1][-1])


iim = lambda : list(map(int, input().rstrip().split()))

def resolve():
	(N, S) = iim()
	A = list(iim())
	mod = 998244353
	S1 = S + 1
	dp = [0] * (S + 1)
	dp[0] = pow(2, N, mod)
	inv = pow(2, mod - 2, mod)
	for ai in A:
		for i in range(S, ai - 1, -1):
			dp[i] = (dp[i] + dp[i - ai] * inv) % mod
	print(dp[-1])

def __starting_point():
	resolve()
__starting_point()


(n, s) = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
dp = [[0] * (s + 1) for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for ss in range(s + 1):
		if ss >= a[i]:
			dp[i + 1][ss] = (dp[i][ss] * 2 + dp[i][ss - a[i]]) % MOD
		else:
			dp[i + 1][ss] = dp[i][ss] * 2 % MOD
print(dp[n][s])


import sys
input = sys.stdin.readline
mod = 998244353
(N, S) = map(int, input().split())
A = list(map(int, input().split()))
inv2 = pow(2, mod - 2, mod)
dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = pow(2, N, mod)
for (i, a) in enumerate(A):
	dp[i + 1] = dp[i][:]
	for s in range(S - a + 1):
		dp[i + 1][s + a] = (dp[i + 1][s + a] + dp[i][s] * inv2) % mod
print(dp[N][S])


(mod1, mod2) = (10 ** 9 + 7, 998244353)
mod = mod2
(n, s) = map(int, input().split())
dp = [0] * (s + 1)
dp[0] = 1
for a in map(int, input().split()):
	dp = [(2 * dp[i] + (0 if i < a else dp[i - a])) % mod for i in range(s + 1)]
print(dp[-1])


(n, s) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
U = 3010
dp = [0] * (U + 1)
dp[0] = 1
for a in A:
	dp2 = [0] * (s + 1)
	for j in range(s + 1):
		dp2[j] = dp[j] * 2
		if j >= a:
			dp2[j] += dp[j - a]
		dp2[j] %= MOD
	dp = dp2
print(dp[s])


def sep():
	return map(int, input().strip().split(' '))

def lis():
	return list(sep())
(n, s) = sep()
ar = lis()
ar.insert(0, 0)
dp = [[0] * (s + 2) for _ in range(n + 2)]
dp[0][0] = 1
N = 998244353
for i in range(1, n + 1):
	for j in range(0, s + 1):
		dp[i][j] = 2 * dp[i - 1][j] % N
		if j - ar[i] >= 0:
			dp[i][j] = (dp[i][j] + dp[i - 1][j - ar[i]]) % N
print(dp[n][s])


def main():
	import sys
	mod = 998244353

	def input():
		return sys.stdin.readline().rstrip()
	(n, s) = map(int, input().split())
	a = list(map(int, input().split()))
	dp = [0] * (s + 1)
	dp[0] = 1
	import numpy as np
	dp = np.array(dp)
	for i in range(n):
		dp[a[i]:] = (2 * dp[a[i]:] % mod + dp[:-a[i]]) % mod
		dp[:a[i]] *= 2
		dp[:a[i]] %= mod
	print(dp[-1])

def __starting_point():
	main()
__starting_point()


(n, s) = map(int, input().split())
(*A,) = map(int, input().split())
p = 998244353
DP = [[0 for j in range(s + 1)] for i in range(n + 1)]
DP[0][0] = 1
for i in range(n):
	for j in range(s + 1):
		if j >= A[i]:
			DP[i + 1][j] = (2 * DP[i][j] + DP[i][j - A[i]]) % p
		else:
			DP[i + 1][j] = 2 * DP[i][j] % p
print(DP[n][s] % p)


import numpy as np
MOD = 998244353
(N, S) = map(int, input().split())
A = np.array(list(map(int, input().split())))
dp = np.zeros((N, S + 1))
dp[0, 0] = 2
if A[0] < S + 1:
	dp[0, A[0]] = 1
for i in range(1, N):
	dp[i, :] = 2 * dp[i - 1, :] % MOD
	if A[i] > S:
		continue
	dp[i, A[i]:S + 1] += dp[i - 1, 0:S - A[i] + 1]
	dp[i, :] %= MOD
print(int(dp[N - 1, S]))


import sys
input = sys.stdin.readline
mod = 998244353
(N, S) = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
dp = [0] * (S + 1)
dp[0] = pow(2, N, mod)
two_inv = pow(2, mod - 2, mod)
for (i, a) in enumerate(A):
	for j in range(a, S + 1)[::-1]:
		dp[j] = (dp[j] + dp[j - a] * two_inv) % mod
print(dp[S])


import numpy as np
mod = 998244353
(n, s) = list(map(int, input().split()))
A = list(map(int, input().split()))
DP = np.zeros(3005, dtype=np.int64)
for (num, a) in enumerate(A):
	double = DP * 2
	shift = np.hstack([np.zeros(a), DP[:-a]]).astype(np.int64)
	DP = double + shift
	DP[a] += pow(2, num, mod)
	DP %= mod
print(DP[s])


K = 96
(N, S) = map(int, input().split())
A = [int(a) for a in input().split()]
P = 998244353
pa = (1 << 64) - (1 << 64) % P
m = int(('1' * 32 + '0' * 64) * 3030, 2)
modP = lambda x: x - ((x & m) >> 64) * pa
s = 1 << K * S
for a in A:
	s = 2 * s + (s >> K * a)
	s = modP(s)
print((s & (1 << K) - 1) % P)


import numpy as np
(n, s) = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
dp = np.zeros(s + 1, dtype=int)
dp[0] = 1
for i in range(n):
	ddp = dp * 2 % MOD
	ddp[a[i]:] += dp[:-a[i]]
	dp = ddp % MOD
print(dp[s])


import sys
input = sys.stdin.readline

def calc():
	mod = 998244353
	(n, s) = map(int, input().split())
	arr = list(map(int, input().split()))
	dp = [0] * (s + 1)
	dp[0] = 1
	ans = 0
	for i in range(1, n + 1):
		val = arr[i - 1]
		for k in range(s, -1, -1):
			dp[k] *= 2
			dp[k] %= mod
			if k >= val and dp[k - val] != 0:
				dp[k] += dp[k - val]
				dp[k] %= mod
	print(dp[s] % mod)
calc()


import sys
readline = sys.stdin.readline
(N, S) = map(int, readline().split())
A = list(map(int, readline().split()))
dp = [[0] * (S + 2) for i in range(N + 1)]
dp[0][0] = 1
mod = 998244353
for (i, a) in enumerate(A):
	for j in range(S + 1):
		if j - a >= 0:
			dp[i + 1][j] = (dp[i][j] * 2 + dp[i][j - a]) % mod
		else:
			dp[i + 1][j] = dp[i][j] * 2 % mod
print(dp[N][S])


import numpy as np
(N, S) = list(map(int, input().split()))
A = list(map(int, input().split()))
mod = 998244353
f = np.zeros(3100, np.int64)
ans = 0
f[0] = 1
for a in A:
	g = f.copy()
	f[a:] += g[:-a]
	f += g
	f %= mod
print(f[S])


from functools import lru_cache
(N, S) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
div = pow(2, MOD - 2, MOD)
DP = [0] * (S + 1)
DP[0] = pow(2, N, MOD)
for a in A:
	for i in range(S - a, -1, -1):
		if DP[i] == 0:
			continue
		DP[i + a] = (DP[i + a] + DP[i] * div) % MOD
print(DP[S])


import numpy as np

def finalFunc(n, s, A):
	var = np.array([0 for i in range(min(3001, s + 1))])
	var[0] = 1
	for i in A:
		tmp = var[:-i].copy()
		var *= 2
		var[i:] += tmp
		var %= 998244353
	return var[s]
(n, s) = map(int, input().split())
A = list(map(int, input().split()))
print(finalFunc(n, s, A))


(n, s) = map(int, input().split())
al = list(map(int, input().split()))
ans = 0
dp = [0 for _ in range(s + 1)]
dp[0] = 1
for i in range(n):
	for k in range(s, -1, -1):
		if k - al[i] < 0:
			dp[k] = 2 * dp[k]
		else:
			dp[k] = 2 * dp[k] + dp[k - al[i]]
		dp[k] %= 998244353
print(dp[-1])


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

def main():
	dp = [0] * (S + 1)
	dp[0] = 1
	for i in range(1, N + 1):
		p = [0] * (S + 1)
		(dp, p) = (p, dp)
		for j in range(0, S + 1):
			dp[j] += 2 * p[j]
			dp[j] %= MOD
			if j - A[i - 1] >= 0:
				dp[j] += p[j - A[i - 1]]
				dp[j] %= MOD
	print(dp[S])
main()


import numpy as np
(n, s) = map(int, input().split())
(*a,) = map(int, input().split())
l = min(s + 1, 3001)
dp = np.zeros(l, dtype=int)
dp[0] = 1
mod = 998244353
ans = 0
cnt = 0
for ai in a:
	dp2 = dp[:-ai].copy()
	dp *= 2
	dp[ai:] += dp2
	dp %= mod
print(dp[s])


import sys
input = sys.stdin.readline
(N, S) = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353
dp = [0] * (S + 1)
dp[0] = 1
md = pow(2, mod - 2, mod)
for i in range(N):
	for x in range(S, -1, -1):
		if dp[x] == 0:
			continue
		if x + a[i] <= S:
			dp[x + a[i]] += dp[x] * md % mod
			dp[x + a[i]] %= mod
print(dp[-1] * pow(2, N, mod) % mod)


from copy import copy
import numpy as np
(N, S) = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = np.zeros(S + 100, np.int64)
dp[0] = 1
for i in range(N):
	buf = copy(dp)
	dp = 2 * dp
	dp[A[i]:] += buf[:-A[i]]
	dp %= 998244353
print(dp[S] % 998244353)


(n, s, *a) = map(int, open(0).read().split())
d = [0] * -~s
m = 998244353
v = pow(2, m - 2, m)
d[0] = pow(2, n, m)
for i in a:
	for j in range(s, i - 1, -1):
		d[j] += d[j - i] * v % m
print(d[s] % m)


import pprint
(N, S) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
dp = [[0 for _ in range(S + 1)] for _ in range(N + 1)]
dp[0][0] = 1
p = 998244353
for i in range(N):
	for j in range(S + 1):
		dp[i + 1][j] = (dp[i + 1][j] + 2 * dp[i][j]) % p
		if j >= A[i]:
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - A[i]]) % p
print(dp[N][S])


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
inv = pow(2, mod - 2, mod)
poly = [0 for i in range(3001)]
poly[0] = 1
for i in range(N):
	for j in range(3000, -1, -1):
		if j >= A[i]:
			poly[j] = inv * poly[j - A[i]] + poly[j]
			poly[j] %= mod
res = pow(2, N, mod) * poly[S]
res %= mod
print(res)


(n, s) = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353
dp = [[0] * (s + 1) for i in range(n + 1)]
dp[0][0] = pow(2, n, mod)
x = pow(2, mod - 2, mod)
for i in range(n):
	for j in range(s + 1):
		if j >= a[i]:
			dp[i + 1][j] = (dp[i][j - a[i]] * x + dp[i][j]) % mod
		else:
			dp[i + 1][j] = dp[i][j] % mod
print(dp[n][s])


def main():
	import sys
	import numpy as np
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 6)
	(N, S) = [int(x) for x in input().strip().split()]
	An = [int(x) for x in input().strip().split()]
	dp = np.zeros(S + 1, dtype=int)
	dp[0] = 2
	if An[0] <= S:
		dp[An[0]] = 1
	for n in range(1, N):
		dp *= 2
		dp[An[n]:] += dp[:-An[n]] // 2
		dp %= 998244353
	print(dp[S])

def __starting_point():
	main()
__starting_point()


(N, S) = map(int, input().split())
A = [int(s) for s in input().split()]
DP = [[0 for j in range(S + 1)] for i in range(N + 1)]
mod = 998244353
DP[0][0] = 1
for i in range(N):
	for j in range(S + 1):
		DP[i + 1][j] += 2 * DP[i][j]
		DP[i + 1][j] %= mod
		if j + A[i] <= S:
			DP[i + 1][j + A[i]] += DP[i][j]
			DP[i + 1][j + A[i]] %= mod
print(DP[N][S])


import numpy as np
MOD = 998244353
(N, S) = list(map(int, input().split(' ')))
A = (0, *list(map(int, input().split(' '))))
dp = np.zeros(shape=(N + 1, S + 1), dtype=int)
dp[0][0] = 1
for i in range(1, N + 1):
	a = A[i]
	dp[i] = 2 * dp[i - 1] % MOD
	dp[i][a:] += dp[i - 1][:-a]
	dp[i] %= MOD
print(dp[N][S])


import numpy as np
(n, s, *a) = map(int, open(0).read().split())
mod = 998244353
d = np.zeros(s + 1, dtype=np.int64)
d[0] = 1
for x in a:
	p = d * 2
	if x <= s:
		p[x:] += d[:s - x + 1]
	p %= mod
	d = p
print(d[-1])


(n, s) = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353
temp = [1] + [0] * s
for i in range(n):
	temp2 = [0] * (s + 1)
	for j in range(s + 1):
		temp2[j] += temp[j] * 2
		temp2[j] %= mod
	for j in range(s + 1 - a[i]):
		temp2[j + a[i]] += temp[j]
		temp2[j + a[i]] %= mod
	temp = temp2
print(temp[s])


def main():
	(N, S) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	return solve(N, S, A)

def solve(N, S, A):
	mod = 998244353
	dp = [0] * (S + 1)
	dp[0] = pow(2, N, mod)
	div2 = pow(2, mod - 2, mod)
	m = 0
	for a in A:
		m += a
		for i in reversed(list(range(a, min(S, m) + 1))):
			dp[i] = (dp[i] + dp[i - a] * div2) % mod
	return dp[S]
print(main())


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
DP = [0] * (S + 1)
DP[0] = pow(2, N, mod)
INV = pow(2, mod - 2, mod)
for a in A:
	for i in range(S - a, -1, -1):
		DP[i + a] = (DP[i] * INV + DP[i + a]) % mod
print(DP[S])


(n, s) = map(int, input().split())
a = [int(i) for i in input().split()]
mod = 998244353
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for k in range(s + 1):
		dp[i + 1][k] += 2 * dp[i][k]
		dp[i + 1][k] %= mod
		if k + a[i] <= s:
			dp[i + 1][k + a[i]] += dp[i][k]
			dp[i + 1][k + a[i]] %= mod
print(dp[n][s])


import numpy as np

def main():
	(n, s) = map(int, input().split())
	a = [int(i) for i in input().split()]
	mod = 998244353
	dp = np.zeros((n + 1, s + 1), dtype=int)
	dp[0][0] = 1
	for i in range(n):
		ai = a[i]
		dp[i + 1] = dp[i] * 2 % mod
		dp[i + 1, ai:] = (dp[i + 1, ai:] + dp[i, :-ai]) % mod
	print(dp[n][s])

def __starting_point():
	main()
__starting_point()


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
import numpy as np
d = np.zeros((N + 1, S + 1), dtype=np.int64)
d[0, 0] = 1
m = 998244353
for i in range(N):
	d[i + 1] = d[i] * 2 % m
	d[i + 1, A[i]:] = (d[i + 1, A[i]:] + d[i, :-A[i]]) % m
print(d[-1, -1])


MOD = 998244353
(N, S) = map(int, input().split())
alist = list(map(int, input().split()))
dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(1, N + 1):
	for k in range(S + 1):
		dp[i][k] = 2 * dp[i - 1][k]
		if k - alist[i - 1] >= 0:
			dp[i][k] += dp[i - 1][k - alist[i - 1]]
		dp[i][k] %= MOD
print(dp[N][S])


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
L = [[0 for i in range(S + 1)] for j in range(N + 1)]
L[0][0] = 1
for (j, a) in enumerate(A):
	for i in range(S + 1):
		if i < a:
			L[j + 1][i] = 2 * L[j][i] % mod
		else:
			L[j + 1][i] = (2 * L[j][i] + L[j][i - a]) % mod
print(L[N][S])


import numpy as np
import sys
sys.setrecursionlimit(10 ** 9)

def mi():
	return map(int, input().split())

def ii():
	return int(input())

def isp():
	return input().split()

def deb(text):
	print('-------\n{}\n-------'.format(text))
INF = 10 ** 20

class Polynomial:

	def __init__(self, dim=0, const=1):
		self.values = [(dim, const)]

	def __add__(self, other):
		return self.values + other.values

class PolySolver:

	def __init__(self, size):
		self.size = size
		self.f = np.zeros(size, np.int64)
		self.f[0] = 1

	def multiple(self, polynomial, MOD):
		new_F = np.zeros(self.size, np.int64)
		for (dim, const) in polynomial:
			if dim != 0:
				g = np.zeros(self.size, np.int64)
				g[dim:] += self.f[:-dim]
			else:
				g = const * self.f.copy()
			new_F += g
		self.f = new_F
		self.f %= MOD

	def get_coefficient(self, dim):
		return self.f[dim]

def main():
	(N, S) = mi()
	A = list(mi())
	MOD = 998244353
	poly = PolySolver(3010)
	for a in A:
		f = Polynomial(const=2) + Polynomial(dim=a)
		poly.multiple(f, MOD)
	print(poly.get_coefficient(S))

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
(N, S) = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
DP = [0] * (S + 1)
DP[0] = pow(2, N, mod)
INV = pow(2, mod - 2, mod)
for a in A:
	for i in range(S - a, -1, -1):
		DP[i + a] = (DP[i] * INV + DP[i + a]) % mod
print(DP[S])


import numpy as np
(N, S) = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
dp = np.array([0] * 3001, dtype=int)
dp[0] = 2
dp[A[0]] = 1
mod = 998244353
for a in A[1:]:
	dpn = np.zeros(3001, dtype=int)
	dpn[a:] = dp[:-a]
	dpn += dp * 2
	dpn %= mod
	dp = dpn
print(dp[S])


(N, S) = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
ans = [[0 for e in range(S + 1)] for f in range(N + 1)]
ans[0][0] = 1
for i in range(N):
	for k in range(S + 1):
		ans[i + 1][k] = ans[i][k] * 2
		ans[i + 1][k] %= mod
	for j in range(A[i], S + 1):
		ans[i + 1][j] += ans[i][j - A[i]]
		ans[i + 1][j] %= mod
print(ans[N][S])