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

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

Solution (Python):
N,S = map(int,input().split())
A = list(map(int,input().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])

Solution (Python):
def main():
    n, s = map(int, input().split())
    mod = 998244353
    a = list(map(int, input().split()))
    dp = [[0]*(s+1) for _ in range(n+1)]
    dp[0][0] = 1
    dio = dp[0]
    for i in range(1, n+1):
        ai = a[i-1]
        di = dp[i]
        for j in range(min(s+1, ai)):
            di[j] = (di[j]+2*dio[j])%mod
        for j in range(ai, s+1):
            di[j] = (di[j]+2*dio[j]+dio[j-ai])%mod
        dp[i] = di
        dio = di
    print(dp[n][s])
    
if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

MOD = 998244353

N, S = map(int, input().split(' '))
A = (0, *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])

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

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

Solution (Python):
mod = 998244353

N, S, *A = map(int, open(0).read().split())

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

for i, a in enumerate(A, 1):
    for j in range(S + 1):
        dp[i][j] = (2 * dp[i - 1][j] + (dp[i - 1][j - a] if j >= a else 0)) % mod

print(dp[N][S])

Solution (Python):
mod = 998244353

N, S, *A = map(int, open(0).read().split())

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[N][S])

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

Solution (Python):
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)
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Solution (Python):
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])
                
if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline

N, S = map(int, readline().split())
A = list(int(x) for x in readline().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+1][j] + dp[i][j] * 2) % MOD
        
        if j + A[i] <= S:
            dp[i+1][j+A[i]] = (dp[i+1][j+A[i]] + dp[i][j]) % MOD
print(dp[N][S])

Solution (Python):
import sys

import numpy as np

input = lambda: sys.stdin.readline().rstrip()
MOD = 998244353

N, S = 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])

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):
        if dp[i][j] != 0:
            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

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __repr__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md=998244353

def main():
    n,s=MI()
    aa=LI()
    dp=[0]*(s+1)
    dp[0]=mint(1)
    for a in aa:
        for i in range(s,-1,-1):
            pre=dp[i]
            if pre==0:continue
            dp[i]+=pre
            if i+a<=s:dp[i+a]+=pre
    print(dp[s])

main()

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353
    N,S=MI()
    A=LI()
    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])
    

            

main()

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):
    a = A[i]
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] * 2
        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])

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**9)
mod = 998244353

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    
    """
    maspyさんの多項式解法も試してみる。
    例えばA = [2, 2, 4]の場合、
        f({1, 2, 3}) = [x^S](1 + x^2)(1 + x^2)(1 + x^4)
        f({1, 2})    = [x^S](1 + x^2)(1 + x^2)
    よって求める答えはf_i = (1 + x^{A[i]})として
        [x^S](f_1 f_2 f_3 + f_1 f_2 + f_2 f_3 + f_3 f_1 + f_1 + f_2 + f_3)
    となる。
    さらにS >= 1なのでこれに1を足しても結果は変わらない。なので因数分解して
        [x^S](1 + f_1)(1 + f_2)(1 + f_3)
    を求めればよい。
    """

    poly = [0] * (S + 1) 
    poly[0] = 1
    for a in A:
        
        poly2 = [poly[i] * 2 % mod for i in range(S + 1)]
        for i in range(S + 1):
            if i + a <= S:
                poly2[i + a] += poly[i]
                poly2[i + a] %= mod
        poly = poly2
    print(poly[S])
    

if __name__ == "__main__":
    main()

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
import random
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=998244353
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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]+=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 sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    N, S = map(int, input().strip().split())
    A = np.fromstring(input().strip(), dtype=np.int32, sep=" ")
    return N, S, A


@njit
def solve(N, S, A, MOD=998244353):
    dp = np.zeros((S+1), dtype=np.int32)
    dp[0] = 1
    for i in range(N):
        for j in range(S, -1, -1):
            v = 2 * dp[j]
            if j - A[i] >= 0:
                v += dp[j-A[i]]
            dp[j] = v % MOD
    return dp[S]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Solution (Python):
mod = 998244353

n,s = map(int, input().split())
al = list(map(int, input().split()))

dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    a = al[i]
    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[n][s])

Solution (Python):
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])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
from functools import lru_cache
sys.setrecursionlimit(10**9)
mod = 998244353

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

    """
    再帰の計算式自体は合っていた！
    メモ化再帰とdpで計算量は変わらないはずだが、取りあえずdpで書き直してみる。
    """

    dp = [[0] * (S + 1) for _ in range(N)] 
    dp[0][0] = 1
    for n in range(1, N): dp[n][0] = (dp[n - 1][0] * 2 + 1) % mod
    for s in range(1, S + 1): dp[0][s] = 1 if s == A[0] else 0
    for n in range(1, N):
        for s in range(1, S + 1):
            dp[n][s] = (dp[n - 1][s] * 2 + dp[n - 1][s - A[n]]) if s >= A[n] else dp[n - 1][s] * 2
            if A[n] == s: dp[n][s] += 1
            dp[n][s] %= mod
    print(dp[N - 1][S])

    

if __name__ == "__main__":
    main()

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

Solution (Python):
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])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 998244353
INF = float('inf')


N, A = MI()
a = [0, *list(map(int, input().split()))]



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

for i in range(1, N + 1):
    for j in range(A + 1):
        if j - a[i] < 0:  
            dp[i][j] = 2 * dp[i - 1][j] % MOD
            continue
        dp[i][j] = (dp[i - 1][j - a[i]] + 2 * dp[i - 1][j]) % MOD
print(dp[N][A])

Solution (Python):
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) for _ in range(N + 1)]
    dp[0][0] = pow(2,N,MOD)
    inv2 = pow(2,MOD - 2,MOD)
    for i,a in enumerate(A):
        for j in range(S + 1):
            if j < a:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = (dp[i][j] + dp[i][j - a] * inv2)%MOD
    print(dp[N][S])
if __name__ == '__main__':
    main()

Solution (Python):


import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
import bisect
from queue import PriorityQueue
import itertools
from copy import deepcopy
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def inputfloatlist(): 
    return list(map(float,input().split()))
def tozero(A):
    ret=[None]*len(A)
    for a in range(len(A)):
        ret[a]=A[a]-1
    return ret
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def ruisekiwa(A):
    ret=[0]*(len(A)+1)
    for a in range(len(A)):
        ret[a+1]=ret[a]+A[a]
    return ret
def getmd(x1,y1,x2,y2):
    return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):
    return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow




def f(A,S):
    dp=[[0 for b in range(S+1)] for a in range(len(A)+1)]
    dp[0][0]=1
    for i in range(1,len(A)+1):
        for s in range(S+1):
            dp[i][s]+=dp[i-1][s]*2
            if s-A[i-1]>=0:
                dp[i][s]+=dp[i-1][s-A[i-1]]
            dp[i][s]%=998244353
    return dp
n,S=inputintlist()
A=inputintlist()
dp=f(A,S)
ans=dp[n][S]
print(ans)

Solution (Python):
n,s = map(int,input().split())
A = list(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):
        if j - A[i] >= 0:
            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[n][s])

Solution (Python):
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
fft = np.fft.rfft
ifft = np.fft.irfft
mod = 998244353

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

dp = np.zeros(U+10, dtype=np.int64)
dp[0] = 1
for a in A:
    newDP = dp.copy() * 2
    newDP[a:] += dp[:-a]
    newDP %= mod
    dp = newDP

print(dp[S])

Solution (Python):
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  
from heapq import heappush, heappop
import bisect

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) 
A = [int(input()) for _ in range(N)] 
lst = [list(map(int,input().split())) for i in range(M)] 
"""

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

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

Solution (Python):
def resolve():
    n, s = 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])


if __name__ == '__main__':
    resolve()

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


if __name__ == '__main__':
    resolve()

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

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

Solution (Python):
def resolve():
    n, s = 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])


if __name__ == '__main__':
    resolve()

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

Solution (Python):


iim = lambda: 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])


if __name__ == "__main__":
    resolve()

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,a in enumerate(A):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]*2
        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])

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 s in range(S+1):
        if s-A[i] >= 0:
            dp[i+1][s] = (dp[i][s] * 2 + dp[i][s-A[i]]) % MOD
        else:
            dp[i+1][s] = dp[i][s] * 2 % 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(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])

Solution (Python):

def solve(N,S,A):
    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    mod = 998244353
    for i, a in enumerate(A, 1):
        for s in range(S+1):
            if s-a >= 0:
                dp[i][s] = (dp[i-1][s] * 2 + dp[i-1][s-a]) % mod
            else:
                dp[i][s] = dp[i-1][s] * 2 % mod
    print(dp[N][S])

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,s = LI()
    aa = LI()

    dp = [0] * (s+1)
    dp[0] = 1
    for a in aa:
        np = [0] * (s+1)
        for i in range(s-a,-1,-1):
            np[i+a] = dp[i]
        for i in range(s+1):
            dp[i] *= 2
            dp[i] += np[i]
            dp[i] %= mod2

    return dp[-1]

print(main())

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

Solution (Python):

from collections import deque
import math


def read(): return input()
def read_int(): return int(input())
def read_array(type=int): return [type(i) for i in input().split()]
def read_tupple(type=None):
    tmp = input().split()
    if type is None: return map(int, tmp)
    assert len(tmp) == len(type)
    return [type[i](tmp[i]) for i in range(len(tmp))]

MOD = 998244353
N, S = read_tupple()
A = read_array()

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]
        if j - A[i] >= 0:
            dp[i + 1][j] += dp[i][j - A[i]]
        
        while dp[i+1][j] > MOD:
            dp[i+1][j] -= MOD
        
print(dp[N][S])

Solution (Python):

from collections import deque
import math


def read(): return input()
def read_int(): return int(input())
def read_array(type=int): return [type(i) for i in input().split()]
def read_tupple(type=None):
    tmp = input().split()
    if type is None: return map(int, tmp)
    assert len(tmp) == len(type)
    return [type[i](tmp[i]) for i in range(len(tmp))]






    























MOD = 998244353
N, S = read_tupple()
A = read_array()

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] = (dp[i + 1][j] + 2 * dp[i][j]) % MOD
        if j - A[i] >= 0:
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - A[i]]) % MOD
print(dp[N][S])