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

s = input().strip()
ret = 0
while 'ABC' in s:
    ret += s.count('ABC')
    s = s.replace('ABC', 'BCA')
print(ret)

### FIXED CODE ###

s = input().strip()
n = len(s)
ret = 0
a = 0
i = 0
while i < n:
    if s[i] == 'A':
        a += 1
        i += 1
    elif s[i] == 'B':
        if i < n - 1 and s[i + 1] == 'C':
            ret += a
            i += 2
        else:
            a = 0
            i += 1
    else:
        a = 0
        i += 1
print(ret)
### BUGGY CODE ###

x=int(input())
a=0
b=0
set5 = set([i**5 for i in range(100)])
set5 = set5 | set([-i**5 for i in range(100)])
while True:
    a += 1
    #calc = a**5 - b**5
    #if calc == x:
    #    print(str(a)+" "+str(b))
    #    break
    #else:
    #    if
    if (a**5-x) in set5:
        if a**5-x < 0:
            b = -int((x-a**5)**(1/5)+0.01)
        else:
            b = int((a**5-x)**(1/5)+0.01)
        print(str(a)+" "+str(b))
        break

### FIXED CODE ###

x=int(input())
a=0
b=0
set5 = set([i**5 for i in range(1000)])
set5 = set5 | set([-i**5 for i in range(1000)])
while True:
    a += 1
    #calc = a**5 - b**5
    #if calc == x:
    #    print(str(a)+" "+str(b))
    #    break
    #else:
    #    if
    temp = (a**5-x)
    if temp in set5:
        if a**5-x < 0:
            b = -int((-temp)**(1/5)+0.01)
        else:
            b = int(temp**(1/5)+0.01)
        print(str(a)+" "+str(b))
        break
### BUGGY CODE ###

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

for i in range(n):
  print(a.index(i+1)+1, end=' ')

### FIXED CODE ###

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

t = [(i,val) for i, val in enumerate(a)]
#print(t)
sorted_tup = sorted(t, key=lambda x: x[1])
#print(sorted_tup)
for tup in sorted_tup:
  print(tup[0]+1, end=' ')
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=10**100
for i in range(1,n):
  x=a[:i]
  y=a[i:]
  ans=min(ans,abs(sum(x)-sum(y)))
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
x=a[0]
y=sum(a[1:])
ans=abs(x-y)
for i in range(1,n-1):
  x+=a[i]
  y-=a[i]
  ans=min(ans,abs(x-y))
print(ans)
### BUGGY CODE ###

import sys

lines = sys.stdin.readlines()

X = lines[0].split(' ')
N = int(X[0])
M = int(X[1])

H = [0 for j in range(N)]
Y = [0 for j in range(N)]
Z =[0]*N

for i in range(N):
    H[i] =int(lines[1].split(' ')[i])

for j in range(M):
    A = int(lines[j+2].split(' ')[0])
    B = int(lines[j+2].split(' ')[1])
    if int(H[A-1]) <= int(H[B-1]):      
      Y[A-1] = -1
    if int(H[B-1]) <= int(H[A-1]):
      Y[B-1] = -1

good = 0
for i in range(N):
    if Y[i] ==0:
        good +=1
print(good)


### FIXED CODE ###

import sys

lines = sys.stdin.readlines()

X = lines[0].split(' ')
N = int(X[0])
M = int(X[1])

H = []
Y = []

H=lines[1].split(' ')

for j in range(M):
    A = int(lines[j+2].split(' ')[0])
    B = int(lines[j+2].split(' ')[1])
    if int(H[A-1]) <= int(H[B-1]):      
      Y.append(A-1)
    if int(H[B-1]) <= int(H[A-1]):
      Y.append(B-1)
Z = len(set(Y))
print(N-Z)
### BUGGY CODE ###

#素直な実装　TLR
MOD = 10 ** 9 + 7
L = list(input())
N = len(L)
# print (N)
n = 0
for l in L:
    n = 2 * n + int(l)

ans = 0
for i in range(n + 1):
    tmp = 1
    for j in range(N):
        if (i >> j) & 1:
            tmp *= 2
    # print (i, tmp)
    ans += tmp
    ans %= MOD

print (ans)



### FIXED CODE ###

# すべて1のところ
# 毎回calc(x)を計算しているから遅い
MOD = 10 ** 9 + 7
L = list(input())
N = len(L)

lst = [-1] * N
def calc(x): #1が続いている桁数
    if x == 0:
        return 1
    tmp_ans = 1
    tmp = 1
    for i in range(1, x):
        tmp = (tmp * (x + 1 - i))//i
        tmp_ans += pow(2, i, MOD) * tmp
        tmp_ans %= MOD

    tmp_ans += pow(2, x, MOD)
    tmp_ans %= MOD
    return tmp_ans

def calc1(x):
    return pow(3, x, MOD)

#ここまでで一番上の桁が0の場合を処理済み（N - 1桁で書ける場合）
ans = calc1(N - 1) + 2
# print (ans)

# 1xxxxxxのxxxxxxの部分を足す必要がある

count = 1
for i in range(1, N):
    if L[i] == '1':
        ans += pow(2, count, MOD) * (calc1(N - 1 - i) + 1)
        count += 1
        ans %= MOD
    
print (ans % MOD)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left


N = int(input())
Pn = [[i,j] for i,j in enumerate(list(map(int, input().split())))]
Pn = sorted(Pn,key=lambda x:-x[1])

In = [Pn[0][0]]
Cn = [0 for _ in range(N+1)]
for i,p in Pn[1:]:
  c = bisect_left(In,i)
  In.insert(c,i)

  # Choose leftside bigger
  if c > 0:
    l,r = 0,0
    if c == 1:
      l = In[c-1]+1
    elif c > 1:
      l = In[c-1]-In[c-2]
    if c == len(In)-1:
      r = N-In[c]
    elif c < len(In)-1:
      r = In[c+1]-In[c]
    Cn[p] += l*r

  # Choose rightside bigger
  if c < len(In)-1:
    l,r = 0,0
    if c == len(In)-2:
      r = N-In[c+1]
    elif c < len(In)-2:
      r = In[c+2]-In[c+1]
    if c == 0:
      l = In[c]+1
    elif c > 0:
      l = In[c]-In[c-1]
    Cn[p] += l*r

ans = 0
for i,c in enumerate(Cn):
  ans += i*c
print(ans)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-



N = int(input())
Pn = list(map(int, input().split()))

In = [0] * (N+1)
for i in range(N):
  In[Pn[i]] = i+1

cnt = 0
l = [0] + [i for i in range(N+1)]
r = [i+1 for i in range((N+1))] + [N+1]

for v in range(1, N+1):
  i = In[v]
  
  l1 = l[i]
  l2 = l[l1]
  r1 = r[i]
  r2 = r[r1]
  cnt += ((l1-l2) * (r1-i) + (i-l1) * (r2-r1)) * v
  
  l[r1] = l1
  r[l1] = r1
    
print(cnt)
### BUGGY CODE ###

import collections
import bisect
N,K,L=map(int,input().split())

RP=[i for i in range(N+1)]
Rsize=[1 for i in range(N+1)]
TP=[i for i in range(N+1)]
Tsize=[1 for i in range(N+1)]

def findR(a):
    if a==RP[a]:
        return a
    else:
        return findR(RP[a])
        
def findT(a):
    if a==TP[a]:
        return a
    else:
        return findT(TP[a])
        
def unionR(b,c):
    B=findR(b)
    C=findR(c)
    if Rsize[B]>=Rsize[c]:
        Rsize[B]+=Rsize[C]
        RP[C]=RP[B]
    else:
        Rsize[C]+=Rsize[B]
        RP[B]=RP[C]

def unionT(b,c):
    B=findT(b)
    C=findT(c)
    if Tsize[B]>=Tsize[c]:
        Tsize[B]+=Tsize[C]
        TP[C]=TP[B]
    else:
        Tsize[C]+=Tsize[B]
        TP[B]=TP[C]
        
for i in range(K):
    p,q=map(int,input().split())
    if findR(p)==findR(q):
        pass
    else:
        unionR(p,q)

for i in range(L):
    r,s=map(int,input().split())
    if findT(r)==findT(s):
        pass
    else:
        unionT(r,s)
        
L=collections.Counter()

for i in range(1,N+1):
    L[findR(i),findT(i)]+=1
#print(L)

ANS=L.items()
ANS=list(ANS)
ANS.sort()
K=[]
V=[]
for i in range(len(ANS)):
    K.append(ANS[i][0])
    V.append(ANS[i][1])
ans=str(V[bisect.bisect_left(K,(findR(1),findT(1)))])
for i in range(2,N+1):
    ans+=" "+str(V[bisect.bisect_left(K,(findR(i),findT(i)))])
print(ans)


### FIXED CODE ###

N,K,L=map(int,input().split())
Road_P=[i for i in range(N+1)]
Road_size=[1 for i in range(N+1)]

def find_road(a):
    if a==Road_P[a]:
        return a
    else:
        return find_road(Road_P[a])
        
def union_road(b,c):
    B=find_road(b)
    C=find_road(c)
    if Road_size[B]>=Road_size[C]:
        Road_P[C]=Road_P[B]
        Road_size[B]+=Road_size[C]
    else:
        Road_P[B]=Road_P[C]
        Road_size[C]+=Road_size[B]

for i in range(K):
    p,q=map(int,input().split())
    if find_road(p)!=find_road(q):
        union_road(p,q)
#print(Road_P)

Rail_P=[i for i in range(N+1)]
Rail_size=[1 for i in range(N+1)]

def find_rail(a):
    if a==Rail_P[a]:
        return a
    else:
        return find_rail(Rail_P[a])
        
def union_rail(b,c):
    B=find_rail(b)
    C=find_rail(c)
    if Rail_size[B]>=Rail_size[C]:
        Rail_P[C]=Rail_P[B]
        Rail_size[B]+=Rail_size[C]
    else:
        Rail_P[B]=Rail_P[C]
        Rail_size[C]+=Rail_size[B]

for i in range(L):
    p,q=map(int,input().split())
    if find_rail(p)!=find_rail(q):
        union_rail(p,q)

#print(Rail_P)

comb={}
for i in range(1,N+1):
    if (find_road(i),find_rail(i)) in comb:
        comb[(find_road(i),find_rail(i))]+=1
    else:
        comb[(find_road(i),find_rail(i))]=1

#print(comb)

for i in range(1,N+1):
    print(comb[(find_road(i),find_rail(i))])
### BUGGY CODE ###

n, m = map(int, input().split())

lis = [""] * (m * 4)
set_P = set() 
for i in range(0, m * 4, 4):
  p, y = map(int, input().split())
  lis[i] = i // 4
  lis[i+1] = p
  lis[i+2] = y
  set_P.add(p)

for p in list(set_P):
  y_lis = []
  for i in range(0, m * 4, 4):
    if lis[i + 1] == p:
      y_lis.append([lis[i], lis[i+2]])
  y_lis.sort(key=lambda y_lis:(y_lis[1]))
  for i, city in enumerate(y_lis):
    lis[city[0]*4 + 3] = i + 1
    
for i in range(0, m*4, 4):
  print("{:0=6}".format(lis[i+1]) + "{:0=6}".format(lis[i+3]))

### FIXED CODE ###

n, m = map(int, input().split())
L = []
for i in range(m):
  L.append([i] + list(map(int, input().split() + ["000000000000"])))
L.sort(key=lambda x:(x[1], x[2]))
#print(L)

counter = 1
city = 0
for i in range(m):
  if city == L[i][1]:
    counter += 1
  else:
    counter = 1
  L[i][3] = str(L[i][1]).zfill(6) + str(counter).zfill(6)
  city = L[i][1]
#print(L)
L.sort(key=lambda x:x[0])
for i in range(m):
  print(L[i][3])
### BUGGY CODE ###

from collections import deque
N,M = map(int, input().split())
edge=[[] for j in range(N+1)]
x = [0] * M
y = [0] * M

#N,M=4,5
#x=[1, 1, 3, 2, 3]
#y=[2, 3, 2, 4, 4]
#edge=[[], [2, 3], [4], [2, 4], []]  

for i in range(M):
    x[i], y[i] = map(int, input().split())
    edge[x[i]].append(y[i])

def g(x):
    q=deque([x])
    move=[[1,0],[-1,0],[0,1],[0,-1]]
    num=-1
    s=False
    while q:
        #print(q)
        for i in range(len(q)):
            b=q.popleft()
            if edge[b]==[]:
                #print(num)
                #print(H*W-kuro-num-1)
                num=num
            else:
                for i in edge[b]:
                    q.append(i)
        num+=1
    return num        
m=0
for i in range(N):
    m=max(m,g(i+1))
print(m)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
 
 
N, M = map(int, input().split())
 
G = [[] for _ in range(N + 1)]
for i in range(M):
    x, y = map(int, input().split())
    G[x] += [y]
# print(G)
 
dp = [-1] * (N + 1)
 
 
def func(n):
    if dp[n] != -1:
        return dp[n]
    cnt = 0
	# 先にノードが存在する場合
	# ノードが存在しない場合は、cnt=0のままforをすっ飛ばす
    for m in G[n]:
        cnt = max(cnt, func(m) + 1)
    dp[n] = cnt
    return cnt
 
 
for i in range(1, N + 1):
    func(i)
 
# print(dp)
print(max(dp))
### BUGGY CODE ###

import sys

n,k = map(int,input().split())
ans = 0;
h = [int(x) for x in input().split()]
for i in range(k):
    if len(h) == 0:
        break;
    m = max(h)
    h.remove(m)


if len(h) > 0:
    ans += sum(h)

print(ans)


### FIXED CODE ###

import sys

n,k = map(int,input().split())
ans = 0;
h = [int(x) for x in input().split()]
h.sort(reverse = True)
h = h[k:]

if len(h) > 0:
    ans += sum(h)

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

from collections import defaultdict
import sys

from scipy.misc import comb

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    S = read().split()
    S = list(map(lambda x: sorted(x.decode('UTF-8')), S))

    A = defaultdict(int)
    for i in range(N):
        s = ''.join(S[i])
        A[s] += 1

    cnt = 0
    for i in A.values():
        cnt += comb(i, 2)

    print(int(round(cnt)))


main()


### FIXED CODE ###

import collections

N = int(input())

s = []
ps = []
for i in range(N):
    ps = sorted(list(input()))
    s.append(''.join(ps))

d = collections.Counter(s)

cnt = 0
for v in d.values():
    if v != 1:
        cnt += int(v * (v-1) / 2)

print(cnt)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split(' ')]

max_value = A.pop(A.index(max(A)))
diff = [max_value]
ans = 0
for i in range(N - 1):
    ans = ans + max(diff)
    n = diff.index(max(diff))
    max_value = A.pop(A.index(max(A)))
    diff[n] = max_value
    diff.insert(n + 1, max_value)

print(ans)

### FIXED CODE ###

import sys
from collections import deque

N = int(sys.stdin.readline())
A = [int(i) for i in sys.stdin.readline().split(' ')]

A.sort(reverse=True)
max_value = A.pop(0)
diff = deque([max_value])
ans = 0
for i in A:
    ans = ans + diff.popleft()
    diff.append(i)
    diff.append(i)

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


N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
P = [0] * N
Q = [1]
n = N - 1
while n > 0:
    for q in Q:
        for i in range(M):
            if AB[i][0] == q:
                if P[AB[i][1] - 1] == 0:
                    P[AB[i][1] - 1] = q
                    Q.append(AB[i][1])
                    AB[i] = [0, 0]
                    n -= 1
            elif AB[i][1] == q:
                if P[AB[i][0] - 1] == 0:
                    P[AB[i][0] - 1] = q
                    Q.append(AB[i][0])
                    AB[i] = [0, 0]
                    n -= 1
print('Yes')
for i in range(1, N):
    print(P[i])

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
R = [[] for i in range(N + 1)]
for i in range(M):
    A, B = map(int, input().split())
    R[A].append(B)
    R[B].append(A)
P = [-1] * (N + 1)
P[1] = 0
Q = deque()
Q.append(1)

while Q:
    v = Q.popleft()
    for r in R[v]:
        if P[r] == -1:
            P[r] = v
            Q.append(r)
print('Yes')
for p in P[2:]:
    print(p)
### BUGGY CODE ###

nk = input('')
n = int(nk.split()[0])
k = int(nk.split()[1])

alist = list(map(int,input('').split()))

pre=0
for i in range(n-k+1):
    result=1
    record=""
    for j in range(k):
        result *= alist[j+i]
#        record += " " + str(alist[j+i])
#    print("[{}/{}]:{} = {}".format(i,i+k-1,result,record))
    if i>0:
        if result > pre:
            print('Yes')
        else:
            print('No')
    pre=result


### FIXED CODE ###

nk = input('')
n = int(nk.split()[0])
k = int(nk.split()[1])

alist = list(map(int,input('').split()))

for i in range(1,n-k+1):
    removed = alist[i-1]
    inserted = alist[i+k-1]
    if inserted > removed:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,m = map(int,input().split())
lr = []; cnt = 0
for i in range(m):
    l,r = map(int,input().split())
    lr.append(list(range(l,r+1)))
for i in range(1, n+1):
    check = 0
    for j in range(m):
        if i in lr[j]:
            check += 1
    if check == m:
        cnt += 1
print(cnt)

### FIXED CODE ###

n,m = map(int,input().split())
L = [0]*m; R = [0]*m; cnt = 0
for i in range(m):
    L[i],R[i] = map(int,input().split())
ml = max(L); mr = min(R)
print(mr-ml+1) if ml <= mr else print(0)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

r, c, k = map(int, input().split())
tizu = [[0 for _ in range(c)] for _ in range(r)]
for _ in range(k):
    rr, cc, v = map(int, input().split())
    tizu[rr - 1][cc - 1] = v
    
dp = [[[0, 0, 0, 0] for _ in range(c)] for _ in range(r)]
dp[0][0][1] = tizu[0][0]

for i in range(r):
    for j in range(c):
        if i != 0:
            dp[i][j][0] = max(dp[i][j][0], max(dp[i - 1][j]))
            dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j]) + tizu[i][j])
        if j != 0:
            dp[i][j][0] = max(dp[i][j][0], dp[i][j - 1][0])
            dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][1], dp[i][j - 1][0] + tizu[i][j])
            dp[i][j][2] = max(dp[i][j][2], dp[i][j - 1][2], dp[i][j - 1][1] + tizu[i][j])
            dp[i][j][3] = max(dp[i][j][3], dp[i][j - 1][3], dp[i][j - 1][2] + tizu[i][j])
print(max(dp[-1][-1]))

    


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    
    r, c, k = map(int, input().split())
    tizu = [0 for _ in range(r * c)]
    for _ in range(k):
        rr, cc, v = map(int, input().split())
        tizu[(rr - 1) * c + (cc - 1)] = v
        
    dp = [[0, 0, 0, 0] for _ in range(c)]
    dp[0][1] = tizu[0]
    
    for i in range(r):
        for j in range(c):
            v = tizu[i * c + j]
            if v:
                if i != 0:
                    tmp = max(dp[j])
                    dp[j] = [tmp, tmp + v, 0, 0]
                if j != 0:
                    tmp0 = dp[j - 1][0]
                    tmp1 = dp[j - 1][1]
                    tmp2 = dp[j - 1][2]
                    lst = [max(dp[j][0], tmp0), max(dp[j][1], tmp1, tmp0 + v), max(tmp2, tmp1 + v), max(dp[j - 1][3], tmp2 + v)]
                    dp[j] = lst
            else:
                if i != 0:
                    tmp = max(dp[j])
                    dp[j] = [tmp, 0, 0, 0]
                if j != 0:
                    lst = [max(dp[j][0], dp[j-1][0]), dp[j-1][1], dp[j-1][2], dp[j - 1][3]]
                    dp[j] = lst
    print(max(dp[-1]))
    
main()
### BUGGY CODE ###

from functools import reduce
n = int(input())
a = list(map(int, input().split()))
ans = reduce(lambda x,y:x*y,a)
print(ans if ans <= 10**18 else '-1')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [i for i in a if i != 1]
ans = 1
if len(b) < 100:
    for i in range(len(b)):
        ans *= b[i]
else:
    ans = 10**18+1
if 0 in b:
    ans = 0
print(ans if ans <= 10**18 else '-1')
### BUGGY CODE ###

# c_00 c_01 c_02
# c_10 c_11 c_12
# c_20 c_21 c_22
# a_0+b_0 a_0+b_1 a_0+b_2
# a_1+b_0 a_2+b_2 a_1+b_2
# a_2+b_0 a_2+b_1 a_2+b_2

c_0 = list(map(int, input().split()))
c_1 = list(map(int, input().split()))
c_2 = list(map(int, input().split()))
c = [c_0,c_1,c_2]

for a_0 in range(100+1):
    for a_1 in range(100+1):
        for a_2 in range(100+1):
            b_0 = c[0][0] - a_0
            b_1 = c[0][1] - a_0
            b_2 = c[0][2] - a_0

            a = [a_0,a_1,a_2]
            b = [b_0,b_1,b_2]
            flag = True
            for i in range(3):
                for j in range(3):
                    if c[i][j] == a[i] + b[j]:
                        continue
                    else:
                        flag = False
            if flag:
                print('Yes')
                exit()
print('No')

### FIXED CODE ###

A = [list(map(int, input().split())) for _ in range(3)]

b2_1 = A[0][1] - A[0][0]
b3_1 = A[0][2] - A[0][0]

if any([b2_1 != A[x][1] - A[x][0] for x in [1, 2]]) or any([b3_1 != A[x][2] - A[x][0] for x in [1,2]]):
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

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

mod = 10**9+7

table = [0 for i in range(60)]
for i in a:
    for t in range(60):
        if i&1:
            table[t] += 1
        i >>= 1

ans = 0
for j, s in enumerate(table):
    ans += s*(n-s)*2**j
    ans %= mod
print(ans)

# -- | 01 | 10 | 11
# 01 | 00 | 11 | 10
# 10 | 11 | 00 | 01
# 11 | 10 | 01 | 00
# 12

# --- | 001 | 100 | 111
# 001 | 000 | 101 | 110
# 100 | 101 | 000 | 011
# 111 | 110 | 011 | 000
# 28

### FIXED CODE ###

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

mod = 10**9+7

ans = 0
p = 1
for i in range(60):
    s = sum(1 for b in a if b&p)
    ans += s*(n-s)*p
    ans %= mod
    p <<= 1
print(ans)
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if x + y + z == s:
                ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k + 1):
    for y in range(k + 1):
        if 0 <= s - x - y <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
*l, = map(int, input().split())
c = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            s = sum([ l[i], l[j], l[k] ])
            m = max(l[i], l[j], l[k])
            if m < s-m:
                c += 1
print(c)

### FIXED CODE ###

import sys
import bisect

n = int(input())
*l, = map(int, input().split())
l.sort()
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        c = bisect.bisect_left(l, l[i] + l[j], j+1)
        ans += c - j - 1

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

N,K=map(int,input().split())
H=list(map(int,input().split()))

dp=[0]+[float('inf')]*(N-1)
for n in range(1,N):
    for i in range(max(0,n-K),n):
        dp[n]=min(dp[n],dp[i]+abs(H[n]-H[i]))

print(dp[N-1])

### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))

dp=[float('inf')]*N
dp[0]=0
dp[1]=abs(H[1]-H[0])

for n in range(2,N):
    if n-K>0:
        dp[n]=min([(dp[i]+abs(H[n]-H[i]))for i in range(n-K,n)])
    else:
        dp[n]=min([dp[i]+abs(H[n]-H[i])for i in range(0,n)])

print(dp[N-1])
### BUGGY CODE ###

s=[int(i) for i in input()]
s.reverse()

a=0
l=[0 for i in range(2019)]
l[0]=1
for i in range(len(s)):
  a+=s[i]*(10**i)
  b=a%2019
  l[b]+=1

answer=0
for i in range(2019):
  answer+=l[i]*(l[i]-1)//2
  
print(answer)

### FIXED CODE ###

s=[int(i) for i in input()]
s.reverse()

a=0
l=[0 for i in range(2019)]
l[0]=1
b=0.1
for i in range(len(s)):
  b=int(b*10)
  b%=2019
  a+=s[i]*b
  a%=2019
  l[a]+=1

answer=0
for i in range(2019):
  answer+=l[i]*(l[i]-1)//2
  
print(answer)
### BUGGY CODE ###

N,K=map(int,input().split())
dp=[0]*(N)
dp[0]=1
mod=998244353
L=list()
for i in range(K):
  a,b=map(int,input().split())
  L.append([a,b])
for i in range(N):
  for j in range(K):
    a,b=L[j]
    if i>=b:
      dp[i]+=sum(dp[i-b:i-a+1])
    elif i>=a:
      dp[i]+=sum(dp[:i-a+1])
    dp[i]%=mod
print(dp[-1])

### FIXED CODE ###

N,K=map(int,input().split())
dp=[0]*(N)
dp[0]=1
mod=998244353
L=list()
for i in range(K):
  a,b=map(int,input().split())
  L.append([a,b])
R=[0,1]
for i in range(1,N):
  for j in range(K):
    a,b=L[j]
    if i>=b:
      dp[i]+=R[i-a+1]-R[i-b]
    elif i>=a:
      dp[i]+=R[i-a+1]
    dp[i]%=mod
  R.append(R[-1]+dp[i])
print(dp[-1])
### BUGGY CODE ###

import copy

N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
S = copy.deepcopy(L)
S.sort()
A = [[] for i in range(N)]
k = 0
j = 1
while (k < M):
  if (S[k][0] == j):
    A[j-1].append(S[k][1])
    k += 1
  else:
    j = S[k][0]
    A[j-1].append(S[k][1])
    k += 1     
for i in range(M):
  if (L[i][1] in A[L[i][0]-1]):
    print(str('0'*(6-len(str(L[i][0]))))+str(L[i][0])+str('0'*(6-len(str(A[L[i][0]-1].index(L[i][1])+1))))+str(A[L[i][0]-1].index(L[i][1])+1))

### FIXED CODE ###

N,M = map(int,input().split())
L = []
for i in range(M):
  L.append(list(map(int,input().split())))
for j in range(M):
  L[j].append(j)
L.sort()
l = L[0][0]
cnt = 0
for k in range(M):
  if l == L[k][0]:
    cnt += 1
    L[k].append(cnt)
  else:
    l = L[k][0]
    cnt = 1
    L[k].append(cnt)
L = sorted(L, key = lambda x:x[2])
for i in range(M):
  print('0'*(6-len(str(L[i][0])))+str(L[i][0])+'0'*(6-len(str(L[i][3])))+str(L[i][3]))
### BUGGY CODE ###

import numpy as np


def main():
    N, S = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    dp = np.zeros((N+1, S+1), dtype=int)

    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
    print(dp[N,S])
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

### FIXED CODE ###

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