Problem:
 Score : 600 points    Problem Statement 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 1 3 4
2 2 4      Sample Output 1 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\} )        Sample Input 2 5 8
9 9 9 9 9      Sample Output 2 0       Sample Input 3 10 10
3 1 4 1 5 9 2 6 5 3      Sample Output 3 3296

Solution (Python):
from collections import defaultdict

n, s = map(int, input().split())
aa = tuple(sorted(map(int, input().split())))

MOD = 998244353
dp = [[0 for i in range(s + 1)] for j 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 + aa[i] <= s:
            dp[i + 1][j + aa[i]] += dp[i][j]
            dp[i + 1][j + aa[i]] %= MOD
print(dp[n][s])

Solution (Python):

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])

Solution (Python):
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):
    dp[i+1][j]+=dp[i][j]*2%mod
    if j-a[i]>=0:
      dp[i+1][j]+=dp[i][j-a[i]]
    dp[i+1][j]%=mod
print(dp[-1][-1])

Solution (Python):
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)

Solution (Python):
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 = 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[-1])

Solution (Python):
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 = 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])

Solution (Python):
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 = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = np.zeros(3003,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
    p[a:] += dp[:-a]
    p %= MOD
    dp = p
print(dp[S])

Solution (Python):
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")












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

Solution (Python):
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])

Solution (Python):
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(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])

Solution (Python):
from sys import stdin
def input():
    return stdin.readline()

def main():
    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(1,N+1) : 
        for j in range(S + 1) : 
            if(j==0):
                dp[i][j]+=pow(2,i,mod)
            else:
                dp[i][j]+=2*dp[i-1][j]
                dp[i][j]%=mod
                if(j-A[i-1]>=0):
                    dp[i][j]+=dp[i-1][j-A[i-1]]
            dp[i][j]%=mod
    print(dp[N][S]%mod)
if __name__=="__main__":
    main()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
from sys import stdin
def input():
    return stdin.readline()

def main():
    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(1,N+1) : 
        for j in range(S + 1) : 
            if(j==0):
                dp[i][j]=pow(2,i,mod)
            else:
                dp[i][j]+=2*dp[i-1][j]
                dp[i][j]%=mod
                if(j-A[i-1]>=0):
                    dp[i][j]+=dp[i-1][j-A[i-1]]
            dp[i][j]%=mod
    print(dp[N][S]%mod)
    




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input():
    return sys.stdin.readline().rstrip("\r\n")


def write(*args, end="\n"):
    for x in args[:-1]:
        sys.stdout.write(str(x) + " ")
    sys.stdout.write(str(args[-1]))
    sys.stdout.write(end)


def r_array():
    return [int(x) for x in input().split()]


def r_int():
    return int(input())


if __name__ == "__main__":
    main()

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
import sys

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

    
    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]

    dp[0][0] = 1

    for i in range(N):
        xi = X[i]
        
        for j in range(S+1):
            dp[i+1][j] += dp[i][j]*2  
            dp[i+1][j] %= MOD
            
            if j+xi > S: continue
            dp[i+1][j+xi] += dp[i][j]
            dp[i+1][j+xi] %= MOD

    print(dp[N][S] % MOD)

main()

Solution (Python):

import sys
MOD = 998244353


def main():
    input = sys.stdin.buffer.readline
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[None] * (s + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(s + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
                continue
            if j > a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a[i - 1]]
            elif j == a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + pow(2, i - 1, MOD)
            else:
                dp[i][j] = dp[i - 1][j] * 2
            dp[i][j] %= MOD
    print(dp[n][s])


if __name__ == '__main__':
    main()

Solution (Python):

def main():
    import sys
    imput = sys.stdin.readline
    
    
    
    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(N):
        for j in range(S+1):
            dp[i+1][j] += dp[i][j] * 2 
            dp[i+1][j] %= mod
            if j >= A[i]:
                dp[i+1][j] += dp[i][j-A[i]]
                dp[i+1][j] %= mod
                    
    print(dp[N][S] % mod)

    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,copy
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

mod = 998244353
n,s = inpl()
a = inpl()
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
        if j - a[i] >= 0:
            dp[i+1][j] += dp[i][j-a[i]]
        dp[i+1][j] %= mod

print(dp[-1][-1])

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

Solution (Python):
import sys
MOD = 998244353


def main():
    input = sys.stdin.buffer.readline
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[None] * (s + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(s + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
                continue
            if j > a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a[i - 1]]
            elif j == a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + pow(2, i - 1, MOD)
            else:
                dp[i][j] = dp[i - 1][j] * 2
            dp[i][j] %= MOD
    print(dp[n][s])


if __name__ == '__main__':
    main()

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

Solution (Python):
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):
    var = arr[i - 1]
    for j in range(0, s + 1):
        dp[i][j] = 2 * dp[i - 1][j]
        dp[i][j] %= mod
        if j - var >= 0 and dp[i - 1][j - var] != 0:
            dp[i][j] += dp[i - 1][j - var]
            dp[i][j] %= mod
print(int(dp[n][s]))

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, S = read_values()
    A = read_list()

    dp = [[0 for _ in range(S + 1)] for _ in range(N + 1)] 
    dp[0][0] = 1

    for i, a in enumerate(A):
        for s in range(S + 1):
            dp[i + 1][s] += 2 * dp[i][s]
            dp[i + 1][s] %= mod
            if s + a <= S: 
                dp[i + 1][s + a] += dp[i][s]
                dp[i + 1][s + a] %= mod
    
    print(dp[N][S])


if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
n, s = map(int, input().split())
a = list(map(int, input().split()))

dp = [[0]*(s+1) for _ 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] += 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[n][s])

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 998244353
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  

N, S = read_ints()
A = read_ints()




'''
dp[i][j]...[,i)の数の中の部分集合で、和をjにすることのできる通りの総数

更新則
dp[i + 1][j] = 2 * dp[i][j] + dp[i][j - A[i]]

∵
A[i]の使い方は3通り
1. 最初の部分集合に選ばれない
2. 部分集合の部分集合に選ばれない
3. Sを構成する和に選ばれる
1,2の遷移先は同じところから来るので×2がつく
'''

dp = [[0] * (S + 1) for _ in ra(N + 1)]
dp[0][0] = 1
for i, j in product(ra(N), ra(S + 1)):
    dp[i + 1][j] = 2 * dp[i][j]
    if j - A[i] >= 0:
        dp[i + 1][j] += dp[i][j - A[i]]
    dp[i + 1][j] %= MOD


print(dp[-1][-1])

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 998244353
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  

N, S = read_ints()
A = read_ints()











'''
dp[i][j]...[,i)の数の中の部分集合で、和をjにすることのできる通りの総数

使う可能性のあるものを全列挙できたらいいなぁ
'''

dp = [[0] * (S + 1) for _ in ra(N + 1)]
dp[0][0] = 1
for i, j in product(ra(N), ra(S + 1)):
    dp[i + 1][j] = 2 * dp[i][j]
    if j - A[i] >= 0:
        dp[i + 1][j] += dp[i][j - A[i]]
    dp[i + 1][j] %= MOD


print(dp[-1][-1])

Solution (Python):
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])

Solution (Python):
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] += 2 * dp[i][j]
        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[-1][-1] % MOD)

Solution (Python):



import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf



import math

import bisect



class ModInt(int):

    MOD = None

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def make_2d_arr(s1, s2, default=0):
    a = [None] * s1
    for i, _ in enumerate(a):
        a[i] = [default] * s2
    return a


if __name__ == '__main__':
    n, s = list(map(int, input().split()))
    data = list(map(int, input().split()))

    ModInt.MOD = 998244353
    dp = [ModInt(0)] * (s + 1)
    dp[0] = 1
    dp_arr = [dp, dp[:]]
    frm = 0
    to = 1

    for i in range(n):
        frm, to = to, frm
        for v in range(s + 1):
            dp_arr[to][v] = dp_arr[frm][v] * 2
            src = v - data[i]
            if src >= 0:
                dp_arr[to][v] += dp_arr[frm][src]
    
    
    print(dp_arr[to][s])

Solution (Python):
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())

Solution (Python):
N,S,*A = map(int, open(0).read().split())
dp = [[0] * (S+1) for _ in range(N+1)]
dp[0][0] = 1
appeared = set([0])
for i in range(1,N+1):
    temp = A[i-1]
    ts = set()
    for x in appeared:
        dp[i][x] += (dp[i-1][x]*2) % 998244353
        if temp + x <= S:
            dp[i][temp+x] += dp[i-1][x]
            if temp + x not in appeared:
                ts.add(temp+x)
    appeared |= ts
print(dp[N][S]%998244353)

Solution (Python):
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
import numpy as np
dp=np.zeros((n+1,3001),int)

dp[0][0]=1 

for i in range(n):
  dp[i+1]+=dp[i]*2
  dp[i+1,a[i]:]+=dp[i,:-a[i]]
  dp[i+1]%=mod
print(dp[n][s])

Solution (Python):
MOD = 998244353
N, S = map(int, input().split())
A = tuple(map(int, input().split()))
table = [[0] * (S + 1) for _ in range(N + 1)]
table[0][0] = 1
for n in range(N):
    for s in range(S + 1):
        now = table[n][s]
        table[n + 1][s] = (table[n + 1][s] + now * 2) % MOD
        if s + A[n] <= S:
            table[n + 1][s + A[n]] = (table[n + 1][s + A[n]] + now) % MOD
print(table[N][S])

Solution (Python):
mod=998244353
n,s=map(int,input().split())
a=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]+=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])

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue

Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  
    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
    for i in range(n):
        for j in range(s+1):
            dp[i + 1][j] += dp[i][j] * 2 % 998244353
            if j - a[i] >= 0:
                dp[i + 1][j] += dp[i][j - a[i]]
            dp[i + 1][j] %= 998244353
            
    print(dp[n][s])
if __name__ == "__main__":
    main()

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
import numpy as np

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

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]
  dp[0][0] = 1
  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      
      if sub >= 0:
        dp[i + 1][j] += dp[i][sub]
      dp[i + 1][j] %= 998244353
  
  print(dp[length][target])
  
solve(N, S, A)

Solution (Python):
N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]
  dp[0][0] = 1
  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      
      if sub >= 0:
        dp[i + 1][j] += dp[i][sub]
      dp[i + 1][j] %= 998244353
  
  print(dp[length][target])
  
solve(N, S, A)

Solution (Python):
n,s = map(int,input().split())
a = tuple(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):
  ai = a[i]
  for j in range(s+1):
    dp[i+1][j] += 2*dp[i][j] 
    dp[i+1][j] %= MOD
    if j+ai <= s:
      dp[i+1][j+ai] += dp[i][j]
      dp[i+1][j+ai] %= MOD
print(dp[n][s])

Solution (Python):
import numpy as np
MOD = 998244353

def main():
    n, s = 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 in range(n):
        dp[i][dp[i] >= MOD] %= MOD
        dp[i+1] += dp[i]*2
        if a[i] <= s:
            dp[i+1][a[i]:] += dp[i][:-a[i]]
    print(dp[n][s]%MOD)

if __name__ == "__main__":
    main()

Solution (Python):
"""
Asの部分集合Tの部分集合Uについて考える

1. Tに属さない
2. Tに属し、Uに属さない
3. Tに属し、Uに属す

の3通り考えられる。
i番目までにおいて、部分集合Uの和がkになる⇨dp[i][k]

遷移としては
dp[i+1][k] = dp[i][k] * 2 
dp[i+1][k+A[i]] += dp[i][k]
"""
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(n):
    a = As[i]
    for j in range(s+1):
        dp[i+1][j] += 2*dp[i][j]
        if j + a <= s:
            dp[i+1][j+a] += dp[i][j]
        dp[i+1][j] %= mod
    
            

ans = 0
print(dp[n][s]%mod)

Solution (Python):
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_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(s+1)):
        if s < j+a:
            continue
        dp[j+a] += dp[j]*inv_2
        dp[j+a] %= MOD

print(dp[-1] % MOD)

Solution (Python):
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_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(s+1)):
        if s < j+a:
            continue
        dp[j+a] += dp[j]*inv_2 % MOD

print(dp[-1] % MOD)

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

print(dp[-1]*pow(2, n, MOD) % MOD)

Solution (Python):
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])