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 copy import copy
import numpy as np
N,S=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)

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

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

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

Solution (Python):
n,s = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
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 x in range(s+1):
        dp[i+1][x] = 2*dp[i][x]
        if x-a[i] >= 0:
            dp[i+1][x] += dp[i][x-a[i]]
        dp[i+1][x] %= mod

print(dp[n][s])

Solution (Python):

from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

hf = pow(2,R-2,R)
n,s = inm()
a = inl()
dp = [[0]*(s+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = pow(2,n,R)
sm = 0
for i in range(1,n+1):
    dp[i] = [x for x in dp[i-1]]
    for j in range(s):
        if dp[i-1][j]>0 and j+a[i-1]<=s:
            dp[i][j+a[i-1]] = (dp[i][j+a[i-1]]+dp[i-1][j]*hf)%R
    
    
print(dp[n][s])

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 998244353
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n2 = [1 for _ in range(3010)]
for i in range(1, 3010):
    n2[i] = n2[i - 1] * 2 % mod

n, s = MAP()
a = LIST()
dp = [[0 for _ in range(s + 1)] for _ in range(n)]
if s >= a[0]:
    dp[0][a[0]] = 1
for i in range(1, n):
    for j in range(1, min(s + 1, a[i])):
        dp[i][j] = dp[i - 1][j] * 2
        dp[i][j] %= mod
    if a[i] <= s:
        dp[i][a[i]] = dp[i - 1][a[i]] * 2 + n2[i]
        dp[i][a[i]] %= mod
    for j in range(a[i] + 1, s + 1):
        dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a[i]]
        dp[i][j] %= mod
print(dp[n - 1][s])

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,s = na()
a = na()
mod = 998244353
dp = [0]*(s+1)
dp[0] = 1

for i in range(n):
    pd = [0]*(s+1)
    for j in range(s+1):
        if j+a[i] <= s:
            pd[j+a[i]] += dp[j]
        pd[j] += dp[j]*2%mod
    dp = pd

print(dp[s]%mod)

Solution (Python):
MOD = 998244353

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, S = ZZ()
    A = ZZ()
    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 A[i] <= j <= S: dp[i+1][j] += dp[i][j-A[i]]
            dp[i+1][j] %= MOD
    print(dp[N][S])

    return

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    mod = 998244353
    n, s = 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()

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 998244353
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n2 = [1 for _ in range(3010)]
for i in range(1, 3010):
    n2[i] = n2[i - 1] * 2 % mod

n, s = MAP()
a = LIST()
dp = [[0 for _ in range(s + 1)] for _ in range(n)]
if s >= a[0]:
    dp[0][a[0]] = 1

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

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

Solution (Python):
import sys
mod = 998244353

def solve():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    A = [int(a) for a in input().split()]
    DP = [[0 for _ in range(S + 1)] for i in range(N)]
    DP[0][0] = 2
    if A[0] <= S: DP[0][A[0]] = 1
    ans = 0
    for i, a in enumerate(A[1:]):
        for s in range(S + 1):
            if DP[i][s] > 0:
                DP[i+1][s] += (DP[i][s] * 2) % mod
                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-1][S])
    

    return 0

if __name__ == "__main__":
    solve()

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

print(dp[N][-1]%mod)

Solution (Python):
mod = 998244353
N, S = map(int,input().split())
A = list(map(int,input().split()))
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] += dp[i][j] * 2
        if j + A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j]
        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 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)

Solution (Python):
import sys
from collections import defaultdict

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]

def main():
    md=998244353
    n,s=MI()
    aa=LI()
    dp=[0]*(s+1)
    dp[0]=1
    inv=pow(2,md-2,md)
    for k,a in enumerate(aa):
        for i in range(s-a,-1,-1):
            dp[i+a]=(dp[i+a]+dp[i]*inv)%md
        
    ans=dp[s]*pow(2,n,md)%md
    print(ans)

main()

Solution (Python):
MOD = 998244353

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

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

p = [[0 for k in range(N + 1)] for j in range(S + 1)]
p[0][0] = 1

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

print(dp[N][S])

Solution (Python):
MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split())))
    prev = [0] * (S+1)
    prev[0] = pow(2, N, MOD)
    half = pow(2, MOD-2, MOD) % MOD
    for i in range(N):
        cur = list(prev)
        for total in range(S+1):
            if total + A[i] > S:
                continue

            cur[total + A[i]] = (cur[total + A[i]] +
                                 prev[total] * half) % MOD
        prev = cur
    print(cur[S])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


from functools import lru_cache


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 998244353
 
    

    
    N, S = map(int, input().split())
    A = tuple(map(int, input().split())) 
    
    
    dp=[0 for _ in range(S+1)]
    dp[0]=pow(2,N,mod)
    i2=pow(2,mod-2,mod)
    for i,a in enumerate(A):
        for s in range(S,a-1,-1):
                dp[s]+=(dp[s-a]*i2)%mod
                dp[s]%=mod
    print(dp[-1]%mod)






if __name__ == "__main__":
    main()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





import copy

N,S = IL()
A = IL()

dic = [0 for i in range(S+1)]
dic[0] = 1

for a in A:
  for i in range(S+1)[::-1]:
    if i<=S:
      dic[i] *= 2
    if i>=a:
      dic[i] += dic[i-a]
print(dic[S]%998244353)

Solution (Python):
MOD = 998244353


def solve(n, s, a_list):
    dp = [[0] * 3001 for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        a = a_list[i]
        for v in range(3001):
            dp[i + 1][v] = (dp[i][v] * 2) % MOD
        for v in range(3001):
            if v + a > 3000:
                break
            dp[i + 1][v + a] = (dp[i + 1][v + a] + dp[i][v]) % MOD
    
    return dp[n][s]


def main():
    n, s = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, s, a_list)
    print(res)


def test():
    assert solve(3, 4, [2, 2, 4]) == 6
    assert solve(5, 8, [9, 9, 9, 9, 9]) == 0
    assert solve(10, 10, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]) == 3296


if __name__ == "__main__":
    test()
    main()

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

Solution (Python):
N,S = map(int,input().split())
*A, = map(int,input().split())

A.sort()

MOD = 998244353

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

Solution (Python):
import sys
from collections import OrderedDict
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    MOD = 998244353
    N, S = inpl()
    A = sorted(inpl())
    dp = {}
    dp[0] = 1
    for i, a in enumerate(A):
        
        ks = sorted(dp.keys())
        for k in ks[::-1]:
            
            if k + a <= S:
                if k + a in dp:
                    dp[k + a] = (dp[k] + dp[k + a]) % MOD
                else:
                    dp[k + a] = dp[k]
            dp[k] = (dp[k] * 2) % MOD
    
    print(0 if S not in dp else dp[S])
    return


if __name__ == '__main__':
    main()

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

Solution (Python):
import sys

input = sys.stdin.buffer.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):
    ni = i + 1
    for j in range(s + 1):
        nj = j
        dp[ni][nj] += 2 * dp[i][j]
        dp[ni][nj] %= mod
        nj = j + A[i]
        if nj <= s:
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
print(dp[n][s] % mod)

Solution (Python):
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(self.power_func(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.power_func(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __row__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def power_func(self,a,n,p):
        bi=str(format(n,"b"))
        res=1
        for i in range(len(bi)):
            res=(res*res) %p
            if bi[i]=="1":
                res=(res*a) %p
        return res

    def combination(self,n,r=-1):
        if r==-1:
            r = n
        
        if (r<0) or (n<r):
            return 0
        cur = ModInt(1)
        res = []
        res.append(cur)
        for i in range(1,r+1):
            cur *= n + 1 -i
            cur /= i
            res.append(cur)
        return res

MOD = 998244353


def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]


def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

N,S = [int(hoge) for hoge in input().split()]
A = [int(hoge) for hoge in input().split()]

DP = [[0]*(S+1) for i in range(N+1)]
DP[0][0] = 1
Modi2 = mod_inv(2,MOD)
for i in range(N):
    a = A[i]
    
    for s,d in enumerate(DP[i]):
        DP[i+1][s] += DP[i][s]
        DP[i+1][s] %= MOD
        Diff = d*Modi2
        Diff %= MOD
        if s + a  <= S:
            DP[i+1][s+a] += Diff
            DP[i+1][s+a] %= MOD

two = ModInt(2)
twotwo = two ** ModInt(N)
print(DP[N][S] * twotwo)

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

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n,s=l_in()
A=l_in()


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

dp[0][0]=1


mod = 998244353

for i in range(1,n+1):
    for w in range(0,s+1):
        dp[i][w] = dp[i-1][w]*2
        a = A[i-1]
        if w >= a:
            dp[i][w] += dp[i-1][w-a]

        dp[i][w] =         dp[i][w]%mod


print(dp[n][s])

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

mod = 998244353

dp = [[0] * 4000 for _ in range(4000)]

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2

    return K * x % mod

inv2 = pow_k(2, mod - 2)
pow2n = pow_k(2, n)

dp[0][0] = pow2n
for i in range(1, n + 1):
    for j in range(s + 1):
        if j >= a[i - 1]:
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - a[i - 1]] * inv2 % mod) % mod
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][s])

Solution (Python):
import sys

LI = lambda: list(map(int, sys.stdin.readline().rstrip().split()))

def main():
    n, s = LI()
    a = LI()
    dp = [[0 for i in range(s+1)] for j in range(n+1)]
    dp[0][0] = 1

    for i in range(n):
        for w in range(s+1):
            dp[i+1][w] = 2*dp[i][w]
            if w >= a[i]:
                dp[i+1][w] += dp[i][w-a[i]]
            dp[i+1][w] %= 998244353

    print(dp[n][s])

if __name__ == '__main__':
    main()

Solution (Python):
def getN():
    return int(input())


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


def getList():
    return list(map(int, input().split()))


from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys


INF = 10 ** 17
MOD = 1000000007

from fractions import *


def inverse(f):
    
    return 1 / f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret


def bunsu(n):
    ret = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            tmp = 0
            while (True):
                if n % i == 0:
                    tmp += 1
                    n //= i
                else:
                    break
            ret.append((i, tmp))

    ret.append((n, 1))
    return ret

MOD = 998244353
def solve():
    n, k = getList()
    nums = getList()
    dp = [0 for i in range(k+1)]
    dp[0] = 1
    for i, num in enumerate(nums):
        new = [0 for i in range(k+1)]
        for j, d in enumerate(dp):
            new[j] += d * 2
            if (j + num) <= k:
                new[j+num] += d

        dp = [ne%MOD for ne in new]
    print(dp[-1])

def main():
    
    
    solve()


if __name__ == "__main__":
    solve()

Solution (Python):

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)

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

def main():
    n,s = map(int,input().split())
    a = list(map(int,input().split()))

    mod = 998244353

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

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

    for i in range(n):
        for j in range(s):
            if i != n-1:
                dp[i+1][j] += dp[i][j] * 2
                dp[i+1][j] %= mod
            if i != n-1 and j + a[i+1] < s:
                dp[i+1][j+a[i+1]] += dp[i][j]
                dp[i+1][j+a[i+1]] %= mod

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

if __name__ == '__main__':
    main()

Solution (Python):
mod = 998244353

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

table = [0]*(s+1)
table[0] = 1
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]
print(ans)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

n,s = readints()
a = readints()

mod = 998244353

z = pow(2,mod-2,mod)

a.sort()

dp = [[0]*(s+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = pow(2,n,mod)

for i in range(1,n+1):
    x = a[i-1]
    for j in range(1,s+1):
        if 0<=j-x:
            dp[i][j] += (dp[i-1][j-x]*z + dp[i-1][j])%mod
        else:
            dp[i][j] += dp[i-1][j]


print(dp[n][s]%mod)

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

lst = [0 for i in range(s+1)]
lst[0] = 1
dp = [lst]
for i in range(n):
    lst = [0 for i in range(s+1)]
    ai = a[i]
    for j in range(s+1):
        if j-ai >= 0:
            lst[j] = (2*dp[-1][j] + dp[-1][j-ai]) % mod
        else:
            lst[j] = (2*dp[-1][j]) % mod
    dp.append(lst)

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

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

Solution (Python):
N,S=map(int,input().split())
A=[0]+list(map(int,input().split()))
       
mod = 998244353

note = [[0 for i in range(S+1)] for n in range(N+1)]

for n in range(1,N+1):
  for i in range(1,S+1):
    if A[n]>i:
      note[n][i] = (note[n-1][i]*2) % mod
    elif A[n] == i:
      note[n][i] = (note[n-1][i]*2 + pow(2,n-1,mod)) % mod
      note[n][i] = note[n][i] % mod 
    else:
      note[n][i] = (note[n-1][i] * 2 + note[n-1][i-A[n]]) % mod
      note[n][i] = note[n][i] % mod
  
print(note[N][S] % mod)

Solution (Python):
import numpy as np

mod = 998244353

n, s = 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])

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

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