Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp[i][j][k] := j番目の要素まで見て、総和がjで、使う区間がk=0,1,2(0:未確定, 1:L確定済, 2:LR確定済)の状態の通り数
dp = list3d(N+1, S+1, 3, 0)
dp[0][0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は全部OK
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            dp[i+1][j+a][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+a][2] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][0] %= MOD
        dp[i+1][j][1] %= MOD
        dp[i+1][j][2] %= MOD
ans = dp[N][S][2]
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp0[i][j][ := j番目の要素まで見て、総和がjで、使う区間が未確定の状態の通り数
dp0 = list2d(N+1, S+1, 0)
# dp1[i][j][ := j番目の要素まで見て、総和がjで、使う区間がL確定済の状態の通り数
dp1 = list2d(N+1, S+1, 0)
# dp2[i][j][ := j番目の要素まで見て、総和がjで、使う区間がLR確定済の状態の通り数
dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は全部OK
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            dp1[i+1][j+a] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+a] += dp0[i][j] + dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [input() for i in range(q)]
point = []
one = []
ans = []

for j in range(n):
  point.append(k)
  one.append(1)
  
for x in range(q):
  point = [p-o for (p,o) in zip(point, one)] 
  point[int(a[x])-1] += 1
  
for y in range(n):
  if point[y] <= 0:
    ans.append('No')
  else:
    ans.append('Yes')
  print(ans[y])

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [input() for i in range(q)]
point = []
ans = []

for z in range(n):
  point.append(0)

for j in range(q):
  point[int(a[j])-1] += 1
  
for x in range(n):
  if point[x] > q-k:
    ans.append('Yes')
  else:
    ans.append('No')
  print(ans[x])
### BUGGY CODE ###

s = input()
x,y = map(int,input().split())
k = 0
data = [[],[]]
f = 0
p = 1
for s_ in s:
    if p==1 and s_=='F':
        x -= 1
        continue
    p = 0
    if s_ == 'T':
        if f:
            data[k].append(f)
        k = (k+1)%2
        f = 0
    else:
        f += 1
if f:
    data[k].append(f)

dpx = [[0]*16001 for _ in range(len(data[0])+1)]
dpy = [[0]*16001 for _ in range(len(data[1])+1)]
dpx[0][8000] = 1
dpy[0][8000] = 1

for i in range(len(data[0])):
    for j in range(len(dpx[i])):
        if dpx[i][j]==1:
            dpx[i+1][j+data[0][i]] = 1
            dpx[i+1][j-data[0][i]] = 1

for i in range(len(data[1])):
    for j in range(len(dpy[i])):
        if dpy[i][j]==1:
            dpy[i+1][j+data[1][i]] = 1
            dpy[i+1][j-data[1][i]] = 1
if dpx[-1][8000+x]==1 and dpy[-1][8000+y]==1:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

now=0
idx=-1
data=[[],[]]
cnt=0
for s in input():
    if s=='F':
        cnt+=1
    elif s=='T':
        if idx==-1:
            now+=cnt
            cnt=0
            idx=1
        elif idx==0:
            data[0].append(cnt)
            cnt=0
            idx=1
        elif idx==1:
            data[1].append(cnt)
            cnt=0
            idx=0
if idx==-1:
    now+=cnt
else:
    data[idx].append(cnt)
def solve(target,move):
    dp={0,}
    for m in move:
        dpc=dp.copy()
        dp=set()
        for k in dpc:
            dp|={k-m,k+m}
    if target in dp:
        return True
    return False
x,y=map(int,input().split())
x-=now
if solve(x,data[0]) and solve(y,data[1]):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())
import numpy as np
arr = np.array(list(set(map(int, input().split()))))

from collections import deque
q = deque([arr])
ans = arr.min()
while len(q) > 0:
    ar = q.popleft()
    ans = min(ar.min(), ans)
    if ans == 1:
        break
    for mon in ar:
        tmp = (ar - 1) % mon + 1
        if np.any(ar != tmp):
            q.append(np.unique(tmp))

print(ans)


### FIXED CODE ###

n = int(input())
from functools import reduce
from fractions import gcd
ans = reduce(gcd, (map(int, input().split())))

print(ans)
### BUGGY CODE ###

A,B,C,D=map(int,input().split())
cnt=0
for j in range(A,B+1):
    if j%C!=0 and j%D!=0:
        cnt+=1  
print(cnt)

### FIXED CODE ###

import fractions

A,B,C,D=map(int,input().split())
c=B//C-(A-1)//C 
d=B//D-(A-1)//D 
l=C*D//fractions.gcd(C,D)
cd=B//l-(A-1)//l
print(int(B-(A-1)-c-d+cd))
### BUGGY CODE ###

import bisect

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

a.sort()

b = [0]*n
ans = 0

for i in range(n):
    if b[-i-1]==0:
        c = 2**(len(bin(a[-i-1]))-2)-a[-i-1]
        d = bisect.bisect_left(a,c)
        e = bisect.bisect_right(a,c)
        if a[d]==c:
            for j in range(d,e):
                if b[j]==0 and j!=n-i-1:
                    ans += 1
                    b[-i-1]=1
                    b[j]=1
                    break

print(ans)


### FIXED CODE ###

import bisect

n = int(input())
aa = list(map(int,input().split()))

aa.sort()

a = [aa[0]]
b = [1]

for i in range(1,n):
    if a[-1]==aa[i]:
        b[-1]+=1
    else:
        a.append(aa[i])
        b.append(1)

ans = 0

for i in range(len(a)):
    while b[-i-1]!=0:
        c = 2**(len(bin(a[-i-1]))-2)-a[-i-1]
        d = bisect.bisect_left(a,c)
        if a[d]==c:
            if b[d]>1:
                ans += 1
                b[-i-1] -= 1
                b[d] -= 1
            elif b[d]==1 and a[d]!=a[-i-1]:
                ans += 1
                b[-i-1] -= 1
                b[d] -= 1
            else:
                break
        else:
            break

print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    R = []
    G = []
    B = []
    for i, s in enumerate(S):
        if s == "R":
            R.append(i)
        elif s == "G":
            G.append(i)
        else:
            B.append(i)
    s = 0
    for i in R:
        for j in G:
            for k in B:
                if abs(i-j) != abs(j-k) and abs(i-j) != abs(k-i) and abs(j-k) != abs(k-i):
                    s += 1
    print(s)
if __name__ == '__main__':
    main()


### FIXED CODE ###

#def main():
#    N = int(input())
#    S = input()
#    R = []
#    G = []
#    B = []
#    for i, s in enumerate(S):
#        if s == "R":
#            R.append(i)
#        elif s == "G":
#            G.append(i)
#        else:
#            B.append(i)
#    s = 0
#    for i in R:
#        for j in G:
#            for k in B:
#                if abs(i-j) != abs(j-k) and abs(i-j) != abs(k-i) and abs(j-k) != abs(k-i):
#                    s += 1
#    print(s)
#if __name__ == '__main__':
#    main()
N = int(input())
S = input()
r = S.count("R")
g = S.count("G")
b = S.count("B")
ans = r*g*b
for i in range(N):
    for j in range(i+1, N):
        k = 2*j -i
        if k >= N:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -=1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
inf = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split(' '))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
score = [0 for _ in range(n)]
visit = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split(' '))
    score[p-1] += x
def addp(num, parent):
    for i in inf[num]:
        if i != parent:
            if i != parent:
                score[i] += score[num]
                addp(i, num)
    return 0
for x in inf[0]:
    score[x] += score[0]
    addp(x, 0)
print(*score)

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

A, B, N = map(int, input().split())
Smx = 0
if B<N:
    N = B
for i in range(N+1):
    S = int((A*(i % B) - ((A*i) % B))/B)
    if Smx<S:
        Smx = S
print(Smx)

### FIXED CODE ###

A, B, N = map(int, input().split())
Smx = 0
if B<N:
    N = B
for i in range(N,0,-1):
    if i<N-A:
        break
    S = int((A*(i % B) - ((A*i) % B))/B)
    if Smx<S:
        Smx = S
print(Smx)
### BUGGY CODE ###

k, s = map(int, input().split())

sum_set = []
for i in range(k + 1):
    for j in range(k + 1):
        for m in range(k + 1):
            if i + j + m == s:
                comb = [i, j, m]
                sum_set.append(comb)
                break
print(len(sum_set))


### FIXED CODE ###

k, s = map(int, input().split())

count = 0
for i in range(k + 1):
    for j in range(k + 1):
        m = s - i - j
        if 0 <= m <= k:
            count += 1
print(count)
### BUGGY CODE ###

s=[int(j) for j in input()][::-1]
m=len(s)
from collections import Counter
c=Counter()
tmp=0
c[0]+=1
t=1
for i in range(m):
    tmp+=t*s[i]
    c[tmp%2019]+=1
    t*=10
ans=0
for i in c:
    j=c[i]
    ans+=j*(j-1)//2

print(ans)

### FIXED CODE ###

s=[int(j) for j in input()][::-1]
c=[0]*2019
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    c[tmp%2019]+=1
    t=t*10%2019
c=np.array(c)
ans=c*(c-1)//2
print(ans.sum())
### BUGGY CODE ###

k = int(input())
n = 10**6
a = "7"

for i in range(n):

    if int(a) % k == 0:
        print(i+1)
        break

    a += "7"
else:
    print("-1")



### FIXED CODE ###

k = int(input())
n = 10**6
a = 0
for i in range(n):
    a *= 10
    a += 7
    a = a % k
    if a == 0:
        print(i+1)
        break


else:
    print("-1")
### BUGGY CODE ###

S = input()
K = int(input())
N = len(S)
C = set()
for i in range(N):
    for j in range(i,N):
        C.add(S[i:j+1])
C = sorted(C)
print(C[K-1])

### FIXED CODE ###

S = input()
K = int(input())
N = len(S)
C = set()
for i in range(N):
    for j in range(i,min(i+K,N)):
        C.add(S[i:j+1])
C = sorted(C)
print(C[K-1])
### BUGGY CODE ###

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

mod = 1000000007
bit = pow(2, 59)
ans = 0
while bit != 0:
    cnt = 0
    for i in range(len(a)):
        if a[i] // bit == 1:
            cnt += 1
        a[i] %= bit
    ans += ((cnt * (n-cnt)) % mod * bit) % mod
    ans %= mod
    bit //= 2

print(ans)

### FIXED CODE ###

import numpy as np
mod = 1000000007

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

bit = 1
ans = 0
for i in range(60):
    a_and = a & 1
    cnt_one = np.count_nonzero(a_and)
    ans += (cnt_one * (n - cnt_one) * bit) % mod
    ans %= mod
    a >>= 1
    bit *= 2
    bit % mod

print(ans)
### BUGGY CODE ###

from collections import (
    deque,
    Counter,
)

N, Q = map(int, input().split(' '))

queue = deque()

for _ in range(1, N):
    queue.append(tuple(map(int, input().split(' '))))

tree = {
    1: set()
}

while len(queue) > 0:
    a, b = queue.popleft()
    if a in tree:
        tree[a].add(b)
        tree[b] = set()
    elif b in tree:
        tree[b].add(a)
        tree[a] = set()
    else:
        queue.append((a, b))

queries = Counter()
for _ in range(Q):
    p, x = map(int, input().split(' '))
    queries[p] += x

stack = deque([1])

results = [0] * (N + 1)

while len(stack) > 0:
    node = stack.popleft()
    results[node] += queries[node]
    for child in tree[node]:
        stack.append(child)
        results[child] += results[node]

print(' '.join([str(result) for result in results[1:]]))


### FIXED CODE ###

from collections import deque, defaultdict

N, Q = map(int, input().split(' '))

tree = defaultdict(set)
for _ in range(1, N):
    a, b = map(int, input().split(' '))
    tree[a].add(b)
    tree[b].add(a)

results = [0] * (N + 1)
for _ in range(Q):
    p, x = map(int, input().split(' '))
    results[p] += x

stack = deque([1])
searched = set()

while len(stack) > 0:
    node = stack.popleft()
    searched.add(node)
    for child in tree[node]:
        if child not in searched:
            stack.append(child)
            results[child] += results[node]

print(' '.join([str(result) for result in results[1:]]))
### BUGGY CODE ###

ta_c,ao_c,num = map(int,input().split())

for i in range(num):
    if ta_c > 0:
        ta_c -=1
    elif ao_c >0:
        ao_c -=1

print("{} {}".format(ta_c,ao_c))


### FIXED CODE ###

ta_c,ao_c,num = map(int,input().split())

if num <= ta_c:
    print(ta_c-num,ao_c)
elif ta_c < num <= ta_c + ao_c:
    ao_c = ta_c+ao_c - num
    ta_c = 0
    print(ta_c,ao_c)
else:
    ta_c, ao_c = 0,0
    print(ta_c,ao_c)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
from collections import *
c=Counter(l)
for i in l:
  d=c.copy()
  d[i]-=1
  a=0
  for j in d.values():
    a+=j*(j-1)//2
  print(a)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
from collections import *
c=Counter(l)
a=sum(i*(i-1)//2 for i in c.values())
for i in l: print(a-c[i]+1)
### BUGGY CODE ###

import collections

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

def main():
    N = Z()
    A = collections.Counter(ZZ())
    e = collections.defaultdict(list)
    l = [False] * (10 ** 6 + 5)

    if 1 in A.keys():
        if A[1] == 1: print(1)
        elif A[1] >= 2: print(0)
        return

    ans = 0
    for n in A.keys():
        l[n] = True
        if A[n] == 1:
            lim = int(n ** 0.5) + 3
            for i in range(1, lim):
                if i * i > n: break
                if n%i != 0: continue
                e[n].append(i)
                if i != n//i: e[n].append(n//i)

    for n in A.keys():
        if A[n] >= 2: continue
        if len(e[n]) == 2:
            ans += 1
            continue
        for p in e[n]:
            if p in {1, n}: continue
            if l[p]: break
        else: ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections

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

def main():
    N = Z()
    A = sorted(ZZ())
    cA = collections.Counter(A)
    MAX_A = 10 ** 6
    is_ok = [True] * (MAX_A + 1)

    if 1 in cA.keys():
        if cA[1] == 1: print(1)
        elif cA[1] >= 2: print(0)
        return

    for a in cA.keys():
        if not is_ok[a]: continue
        if cA[a] >= 2: is_ok[a] = False
        for i in range(2, MAX_A + 1):
            if a * i > MAX_A: break
            is_ok[a * i] = False

    ans = 0
    for a in cA.keys():
        if is_ok[a]: ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())

def calc(m):
    result = 0
    for i in range(1, 41):
        for j in range(1, 41):
            for k in range(1, 41):
                if i**2 + j**2 + k**2 + i*j + j*k + k*i == m:
                    result += 1

    print(result)

for p in range(1, n+1):
    calc(p)

### FIXED CODE ###

n = int(input())
N = 10 ** 4

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

for i in range(1, 42):
    for k in range(1, 99):
        for j in range(i, k+1):
            s = i**2 + j**2 + k**2 + i*j + j*k + k*i
            if s > N:
                continue
            d = len(set([i, j, k]))
            if d == 3:
                l[s] += 6
            elif d == 2:
                l[s] += 3
            elif d == 1:
                l[s] += 1

for i in range(1, n+1):
    print(l[i])
### BUGGY CODE ###

n, m = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10**9 + 7

DP = [[0] * n for _ in range(m)]

t0 = T[0]
count = 0
for i in range(n):
    if S[i] == t0:
        count += 1
    DP[0][i] = count

s0 = S[0]
count = 0
for j in range(m):
    if T[j] == s0:
        count += 1
    DP[j][0] = count

for j in range(1, m):
    for i in range(1, n):
        total = DP[j-1][i] + DP[j][i-1] - DP[j-1][i-1]
        if T[j] == S[i]:
            total += DP[j-1][i-1] + 1
        total %= mod
        DP[j][i] = total

ans = DP[m-1][n-1] + 1
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10**9 + 7

DP = [[0] * n for _ in range(m)]

t0 = T[0]
count = 0
for i in range(n):
    if S[i] == t0:
        count += 1
    DP[0][i] = count

s0 = S[0]
count = 0
for j in range(m):
    if T[j] == s0:
        count += 1
    DP[j][0] = count

for j in range(1, m):
    for i in range(1, n):
        total = DP[j-1][i] + DP[j][i-1] - DP[j-1][i-1]
        if T[j] == S[i]:
            total += DP[j-1][i-1] + 1
        total %= mod
        DP[j][i] = total

ans = DP[m-1][n-1] + 1
print(ans)
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 998244353
def main():
    n,s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[[] for _ in range(s+1)] for _ in range(n+1)]
    dp[0][0].append([-1])
    ans = 0
    for i in range(n):
        for j in range(s,-1,-1):
            if j-a[i] < 0:
                continue
            if dp[i][j-a[i]] == []:
                continue
            for k in range(len(dp[i][j-a[i]])):
                x = copy.deepcopy(dp[i][j-a[i]][k])
                x.append(i)
                dp[i+1][j].append(x)
            if j == s and len(dp[i+1][j]):
                for e in dp[i+1][j]:
                    LEN = len(e)
                    LEN -= 1
                    ans += pow(2,n-LEN,mod)
                    ans %= mod
        for j in range(s-1,-1,-1):
            for k in range(len(dp[i][j])):
                dp[i+1][j].append(dp[i][j][k])
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
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
def main():
    n,s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
    dp[0][0] = pow(2,n,mod)
    MODINV2 = mod_inv(2,mod)
    ans = 0
    for i in range(n):
        for j in range(s,-1,-1):
            if j-a[i] < 0:
                continue
            dp[i+1][j] += dp[i][j-a[i]]*MODINV2
            dp[i+1][j] %= mod
        for j in range(s,-1,-1):
            if j == s:
                ans += dp[i+1][j]
                ans %= mod
            else:
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

for a in A:
    for j in reversed(range(W_MAX+1)):
        if W_MAX < j+a:
            continue
        dp[j+a] += dp[j]*pow(2, MOD-2, MOD)

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

### FIXED CODE ###

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)
### BUGGY CODE ###

n,_,*a=map(int,open(0).read().split())
c,d=1,0
for i in range(n):n=(c+d)%(10**9+7)*(not-~i in a);c,d=n,c
print(n)

### FIXED CODE ###

n,_,*a=map(int,open(0).read().split())
a=set(a)
c,d=1,0
for i in range(n):n=(c+d)%(10**9+7)*(not-~i in a);c,d=n,c
print(n)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, raw_input().split())

ans = []
for _ in range(N):
    a, b = map(int, raw_input().split())
    ans = ans + [a] * b

ans.sort()
print ans[K - 1]


### FIXED CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, raw_input().split())

ab = [[0, 0]] * N
for i in range(N):
    _a, _b = map(int, raw_input().split())
    ab[i] = [_a, _b]
ab.sort(key=lambda x:x[0])

j = 0
index = 0
while j < K:
    j += ab[index][1]
    if j < K:
        index += 1

print ab[index][0]
### BUGGY CODE ###

import itertools

n = int(input())
num_list = list(map(int, input().split()))
sum = 0

for i in itertools.combinations(num_list, 2):
    sum += (i[0] * i[1]) % (10**9 + 7)
    sum % (10**9 + 7)

print(sum % (10**9 + 7))

### FIXED CODE ###

from itertools import accumulate

n = int(input())
a = list(map(int, input().split()))
b = list(accumulate(a))
sum = 0

for i in range(len(a)):
    sum += a[i]*(b[-1] - b[i])
    sum %= 10**9 + 7

print(sum)
### BUGGY CODE ###

n = int(input())
word = [input() for i in range(n)]
test = list([x,word.count(x)] for x in set(word))
max_num = int(max(test, key=lambda x: x[1])[1])
print('\n'.join(sorted([num[0] for num in test if int(num[1]) == max_num])))


### FIXED CODE ###

from collections import Counter
n = int(input())
word = Counter([input() for i in range(n)]).most_common()
print('\n'.join(sorted([num[0] for num in word if int(num[1]) == word[0][1]])))
### BUGGY CODE ###

k = int(input())

if k%2==0:
    print('-1')
    exit()

if k%7==0:
    k//=7

mod = 1
i=1
while mod%k!=0:
    mod+=pow(10,i,k)
    mod%=k
    i+=1
print(i)


### FIXED CODE ###

k = int(input())

if k%2==0:
    print('-1')
    exit()

if k%7==0:
    k//=7

mod = 1
i=1
mod2 =1
while mod%k!=0 and i<=100000000:
    mod1 = mod2*10%k
    mod+=mod1
    mod%=k
    mod2=mod1
    i+=1
if i>=100000000:
    i=-1
print(i)