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

import bisect
 
N = int(input())
Ls = list(map(int, input().split(" ")))
Ls.sort()
 
ans = 0
 
for i in range(N-1,1,-1):
  for j in range(i-1,0,-1):
    if 2*Ls[j] <= Ls[i]:
      break
    ans += (len(Ls[:j]) - bisect.bisect_right(Ls[:j],Ls[i]-Ls[j]))
       
print(ans)

### FIXED CODE ###

import bisect
 
N = int(input())
Ls = list(map(int, input().split(" ")))
Ls.sort()
 
ans = 0
 
for i in range(0,N-2):
  for j in range(i+1,N-1):
    k = bisect.bisect_left(Ls,Ls[i]+Ls[j])
    ans += k - (j + 1)
       
print(ans)
### BUGGY CODE ###

import heapq

N,M = map(int,input().split())
value = list(map(int,input().split()))
value = list(map(lambda x: x*(-1), value))

for i in range(M):
  heapq.heapify(value)
  num = (heapq.heappop(value)*(-1)//2)*(-1)
  heapq.heappush(value,num)

print(sum(list(map(lambda x: x*(-1), value))))

### FIXED CODE ###

import heapq as hp
n, m = map(int, input().split())
list_A = list(map(int, input().split()))
 
a_q = []
for i in list_A:
    hp.heappush(a_q, -1*i)
    
for i in range(m):
    tmp = hp.heappop(a_q)
    tmp = hp.heappush(a_q, int(tmp/2))
    
print(-sum(a_q))
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
ans = 0
for i in range(N-K+1):
    ans = max(ans, sum(p[i:i+K]))
print((ans+K)/2)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
ans,num = sum(p[0:K]),sum(p[0:K])
for i in range(N-K):
    num = num + p[i+K] - p[i]
    ans = max(ans, num)
print((ans+K)/2)
### BUGGY CODE ###

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

dp = [False] * (K + 1)
for i in range(1, K + 1):
    for a in A:
        if i - a >= 0:
            dp[i] |= not dp[i - a]

if dp[K]:
    print("First")
else:
    print("Second")

### FIXED CODE ###

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

dp = [False] * (K + 1)
for i in range(1, K + 1):
    for a in A:
        if i - a >= 0:
            dp[i] |= not dp[i - a]

if dp[K]:
    print("First")
else:
    print("Second")
### BUGGY CODE ###

N, M = map(int,input().split())

P=list(map(int,input().split()))

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


Y=[set() for i in range(N)]
Unstacked=list(range(M))

Y[0]=Y[0]|Swap[0]
Unstacked.remove(0)
j=0
k=0

while Unstacked!=[]:
    while j <len(Unstacked):

        if Y[k] & Swap[Unstacked[j]] !=set():

            Y[k]=Y[k]|Swap[Unstacked[j]]
            Unstacked.remove(Unstacked[j])
            j=0

        else:
            j+=1

    if Unstacked!=[]:
        
        k+=1
        Y[k]=Swap[Unstacked[0]]
        Unstacked.remove(Unstacked[0])

Other=set(range(1,N+1))
for l in range(k+1):
    Other=Other - Y[l]

Other=list(Other)

count=0

for i in range(k+1):
    for j in list(Y[i]):
        if P[j-1] in Y[i]:
            count+=1
        

for m in Other:
    if P[m-1]==m:
        count+=1

print(count)

### FIXED CODE ###

N, M = map(int,input().split())
P=list(map(int,input().split()))

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


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

for i in range(N):
    if find(P[i])==find(i+1):
        count+=1


print(count)
### BUGGY CODE ###

n = int(input())
a = []
for i in input().split():
  a.append(i)
  a = a[::-1]

print(" ".join(list(map(str, a))))



### FIXED CODE ###

n=int(input())
a=[i for i in input().split()]

b=[]
c=[]
if n%2==0:
    for i in range(n):
        if i%2==0:
            b.append(a[i])
        else:
            c.append(a[i])
else:
    for i in range(n):
        if i%2==0:
            c.append(a[i])
        else:
            b.append(a[i])
c=c[::-1]
print(" ".join(c)+" "+" ".join(b))
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
l=[0]*Q
r=[0]*Q
for i in range(Q):
  l[i],r[i]=map(int,input().split())
answer=[0]*Q
for j in range(Q):
  x=l[j]
  counter=[]
  leng=r[j]-l[j]+1
  counter=[1 if (i!=leng-1)and(S[x-1+i]=="A")and(S[x+i]=="C") else 0 for i in range(leng)]
  answer[j]=sum(counter)
for i in range(Q):
  print(answer[i])


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
l=[0]*Q
r=[0]*Q
for i in range(Q):
  l[i],r[i]=map(int,input().split())
counter=[0]*N
for i in range(N-1):
  if S[i]=="A":
    counter[i]=counter[i-1]+(S[i+1]=="C")
  else:counter[i]=counter[i-1]
for j in range(Q):
  print(counter[r[j]-2]-counter[l[j]-2])
### BUGGY CODE ###

y=int(input())
b=[[i,j,k]  for i in range(1,y+1) for j in range(1,y+1) for k in range(1,y+1) ]
c=[]
for l in range(y**3):
    import math
    a = b[l]
    ans = a[0]
    for i in range(1, 2):
        ans1 = math.gcd(ans, a[1])
        ans2 =math.gcd(ans,a[2])
        ans3 =math.gcd(ans1,ans2)
    c.append(ans3)
print(sum(c))   

### FIXED CODE ###

import math
y=int(input())
cnt=0
for i in range (1,y+1):
    for k in range(1,y+1):
        for j in range(1,y+1):
            a = [i,j,k]#リスト
            ans = a[0]
            for x in range(len(a)):
                ans = math.gcd(ans, a[x])
            cnt+=ans
print(cnt)
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
can_n = [0]*n
for i in range(n):
    can = 0
    for j in range(n-i-1):
        left = i+j
        right = left+1
        if h[left] >= h[right]:
            can += 1
        else:
            break
    can_n[i] = can
print(max(can_n))

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
can = 0
max_h = h[0]
max_c = 0
for i in range(n-1):
    l = h[i]
    r = h[i+1]
    if l >= r:
        can += 1
    else:
        can = 0
        max_h = r
    if can > max_c:
        max_c = can
print(max_c)
### BUGGY CODE ###

from itertools import accumulate as acc

H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]

acc_list = [list(acc([0] + s)) for s in S]

# print(acc_list)

def solve(l, x, limit):
    part_num = len(l)-1
    ok, ng = x, W+1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        score = 0
        for i in range(part_num):
            s = 0
            for j in range(l[i], l[i+1]):
                # print(i, j, mid)
                s += acc_list[j][mid] - acc_list[j][x]
            score = max(s, score)
        if score <= limit:
            ok = mid
        else:
            ng = mid
    return ok

min_num = 10**18
for i in range(1<<(H-1)):
    l = []
    for j in range(H-1):
        if (i>>j)&1:
            l.append(j+1)
    h_split_num = len(l)
    l = [0] + l + [H]
    x = solve(l, 0, K)
    w_split_num = 0
    while x < W:
        w_split_num += 1
        x = solve(l, x, K)
    split_num = w_split_num + h_split_num
    min_num = min(split_num, min_num)

print(min_num)

### FIXED CODE ###

from itertools import accumulate as acc

H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]

acc_list = [list(acc([0] + s)) for s in S]

def solve(l, x, limit):
    part_num = len(l)-1
    ok, ng = x, W+1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        score = 0
        for i in range(part_num):
            s = 0
            for j in range(l[i], l[i+1]):
                # print(i, j, mid)
                s += acc_list[j][mid] - acc_list[j][x]
            score = max(s, score)
        if score <= limit:
            ok = mid
        else:
            ng = mid
    return ok

min_num = 10**18
for i in range(1<<(H-1)):
    l = []
    for j in range(H-1):
        if (i>>j)&1:
            l.append(j+1)
    h_split_num = len(l)
    l = [0] + l + [H]
    x = solve(l, 0, K)
    w_split_num = 0
    flag = True
    while x < W:
        w_split_num += 1
        r = solve(l, x, K)
        if x == r:
            flag = False
            break
        x = r
    if flag:
        split_num = w_split_num + h_split_num
        min_num = min(split_num, min_num)

print(min_num)
### BUGGY CODE ###

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

N = int(input())

count = 0
for A in range(1, N+1):
    head_A = str(A)[0]
    tail_A = str(A)[-1]
    for B in range(1, N+1):
        head_B = str(B)[0]
        tail_B = str(B)[-1]
        if head_A == tail_B and tail_A == head_B:
            count += 1

print(count)


### FIXED CODE ###

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

# input
N = int(input())

# create and init dictionary
heads_and_tails = {}
for head in range(1, 10):
    for tail in range(1, 10):
        heads_and_tails[(head, tail)] = 0

# create dictionary contents
for num in range(1, N+1):
    if num%10 == 0:
        continue
    head = int(str(num)[0])
    tail = int(str(num)[-1])
    heads_and_tails[(head, tail)] +=1

# count
count = 0
for head in range(1, 10):
    for tail in range(1, 10):
        count += heads_and_tails[(head, tail)] * heads_and_tails[(tail, head)]

print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
if 0 in A:
    print (0)
    exit(0)
x=1
for i in A:
    x=x*i
if x>10**18:
    print(-1)
    exit(0)
print(x)

### FIXED CODE ###

N = int(input())
L = input().split()
 
 
def mult():
    if "0" in L:
        return 0
    else:
        a = 1
        for i in L:
            a = a * int(i)
            if a > 1000000000000000000:
                return -1
        return a
 
print(mult())
### BUGGY CODE ###

K, N = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
for i in range(len(A)):
    ans.append(max(A) - min(A))
    A[i] += K

print(min(ans))


### FIXED CODE ###

import sys
import random

def test(K, N, A):
    ans = []
    maxp = N-1
    minp = 0
    for i in range(len(A)):
        ans.append(A[maxp] - A[minp])
        A[i] += K
        maxp = (maxp + 1) % (N)
        minp = (minp + 1) % (N)
    print(min(ans))

if __name__ == "__main__":
    if "random" in sys.argv:
        K = int(random.random() * 20000)
        N = int(random.random() * 65536)
        A = sorted([int(random.random() * K) for _ in range(N)])
    else:
        K, N = [int(x) for x in input().split()]
        A = [int(x) for x in input().split()]
    test(K,N,A)
    pass
### BUGGY CODE ###

import copy

n = int(input())
a = list(map(int, input().split()))
size = max(a)
a.sort()
a2 = copy.copy(a)
b = [0] * (size + 1)
while a:
    test = a.pop(0)
    count = 1
    if not a:
        pass
    else:
        while a[0] == test:
            a.pop(0)
            count += 1
            if not a:
                break
    for i in range(size // test):
        b[test * (i + 1)] += count
ans = 0
for i in range(n):
    if b[a2[i]] == 1:
        ans += 1
print(ans)

### FIXED CODE ###

import copy, collections

n = int(input())
a = list(map(int, input().split()))
size = max(a)
a.sort()
a = collections.deque(a)
a2 = copy.copy(a)
b = [0] * (size + 1)
while a:
    test = a.popleft()
    count = 1
    if not a:
        pass
    else:
        while a[0] == test:
            a.popleft()
            count += 1
            if not a:
                break
    for i in range(size // test):
        b[test * (i + 1)] += count
ans = 0
for i in range(n):
    if b[a2[i]] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

s=input()
q= int(input())
 
for iq in range(1,q+1):
	t=input().split()
	if t[0]=='1':
		s=s[::-1]
	else:
		if t[1]=='1':
#			s=t[2]+s
#			s=f"{t[2]}{s}"
			list1=[t[2],s]
			s="".join(list1)
		else:
#			s=s+t[2]
#			s=f"{s}{t[2]}"   
			list2=[s,t[2]]
			s="".join(list2)
 
print (s)


### FIXED CODE ###

s=input()
q= int(input())

top=""
btm=""

iturn=0
for iq in range(1,q+1):
	t=input().split()
	if t[0]=='1':
		iturn=iturn+1   	
	else:
		iturn2=iturn%2
		if (t[1]=='1' and iturn2==0) or (t[1]=='2' and iturn2==1):
#			s=t[2]+s
#			s='{}{}'.format(t[2],s)
			top=t[2]+top
		else:
#			s=s+t[2]
#			s='{}{}'.format(s,t[2])
			btm=btm+t[2]

if iturn%2==0:
	s=top+s+btm
else:
	s=btm[::-1]+s[::-1]+top[::-1]
print (s)
### BUGGY CODE ###

N = int(input())

sum = 0

while N >= 1 :
    sum += N % 10
    N = N // 10
    if(sum > 100) :
      sum = sum % 9

if(sum % 9 == 0) :
    print("Yes")
else :
    print("No")


### FIXED CODE ###

N = int(input())

if N % 9 == 0 :
  print("Yes")
else :
  print("No")
### BUGGY CODE ###

def root(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf[x])
        return uf[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,input().split())
p = list(map(int,input().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,input().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
match = [[] for i in range(N+1)]
for i in range(1, N+1):
    match[uf[i]].append(i)
for i in range(1, N+1):
    matchlen = len(match[i])
    for j in range(matchlen):
        if p[match[i][j]] in match[i]:
            ans += 1
print(str(ans))

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def root(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf[x])
        return uf[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,readline().split())
p = list(map(int,readline().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,readline().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
#N += 1
#match = [[] for i in range(N)]
#for i in range(1, N):
#    match[uf[i]].append(i)
#for i in range(1, N):
#    matchlen = len(match[i])
#    for j in range(matchlen):
#        if p[match[i][j]] in match[i]:
#            ans += 1

for i in range(1, N+1):
    if same(i, p[i]):
        ans += 1
print(str(ans))
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]
res = [0]*4
ans = 10**18
for i in range(1, n - 1):
    for j in range(0, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        for k in range(i + 1, n):
            res[2] = F[k] - F[i]
            res[3] = F[n - 1] - F[k]
            ans = min(ans, max(res) - min(res))
print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]


res = [0]*4
data = [10 ** 18] * 2
ex = [0]*4
ans = 10 ** 18
s = 0
t = 2
for i in range(1, n - 2):
    bl = [True, True]
    for j in range(s, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        if not bl[0]:
            break
        if data[0] > abs(res[1] - res[0]) or j == s:
            s = j
            ex[0] = res[0]
            ex[1] = res[1]
            data[0] = abs(res[1] - res[0])
        else:
            bl[0] = False
    for k in range(t, n):
        res[2] = F[k] - F[i]
        res[3] = F[n - 1] - F[k]
        if not bl[1]:
            break
        if data[1] > abs(res[3] - res[2]) or k == t:
            t = k
            ex[2] = res[2]
            ex[3] = res[3]
            data[1] = abs(res[3] - res[2])
        else:
            bl[1] = False
    ans = min(ans, max(ex) - min(ex))

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

k,s = map(int,input().split())
count = 0
for x in range(max(0,s-2*k),k+1): 
    if x==s:
        count+=1
    else:
        for y in range(max(0,s-k-x),k+1):
            if x+y==s:
                count+=1
            else:
                for z in range(max(0,s-x-y),k+1):
                    if x+y+z == s:
                       count+=1
                       break
print(count)

### FIXED CODE ###

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

n = int(input())
def factorization(num):
    result = []
    temp = num
    for i in range(2, int(num ** 0.5) + 1):
        while temp % i == 0:
            temp = int(temp / i)
            result.append(i)

    if temp != 1:
        result.append(temp)
    if result == []:
        result.append(num)
    return result
factors = factorization(n)
ans = 1000000000000
for i in range(2 ** len(factors)):
    f0, f1 = 1, 1
    for j in range(len(factors)):
        if i >> j & 1:
            f1 *= factors[j]
        else:
            f0 *= factors[j]
    ans = min(ans, f0 + f1 - 2)
print(ans)

### FIXED CODE ###

from itertools import product
n = int(input())
def factorization(num):
    result = []
    count = 0
    temp = num
    for i in range(2, int(num ** 0.5) + 1):
        if temp % i == 0:
            count = 0
            while temp % i == 0:
                count += 1
                temp /= i
            result.append([i, count])
    if temp != 1:
        result.append([temp, 1])
    if result == []:
        result.append([num, 1])
    return result
factors = factorization(n)
exps = [range(factor[1] + 1) for factor in factors]
ans = 1001001001001
for exp0 in product(*exps):
    f0 = 1
    for i in range(len(exp0)):
        f0 *= factors[i][0] ** exp0[i]
    f1 = n // f0
    ans = min(ans, f0 + f1 - 2)
print(int(ans))
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
    w, v = map(int, input().split())
    for w_lim in range(W+1):
        if w <= w_lim:
            dp[i+1][w_lim] = max(dp[i][w_lim-w]+v, dp[i][w_lim])
        else:
            dp[i+1][w_lim] = dp[i][w_lim]
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
    w, v = map(int, input().split())
    for w_lim in range(W+1):
        if w <= w_lim:
            dp[i+1][w_lim] = max(dp[i][w_lim-w]+v, dp[i][w_lim])
        else:
            dp[i+1][w_lim] = dp[i][w_lim]
print(dp[N][W])
### BUGGY CODE ###

K = int(input())


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


ans = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ans += gcd(gcd(a, b), c)

print(ans)


### FIXED CODE ###

from fractions import gcd
K = int(input())


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


ans = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ans += gcd(gcd(a, b), c)

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

N, C = [int(i) for i in input().split(" ")]
x = [0]
v = [0]
for i in range(N):
    t = [int(i) for i in input().split(" ")]
    x.append(t[0])
    v.append(t[1])
x.append(C)
v.append(0)
    

right_cal = [0 for i in range(N + 2)]
for i in range(1, N + 1):
    right_cal[i] = (v[i] + right_cal[i - 1] - x[i] + x[i - 1])
    
left_cal = [0 for i in range(N + 2)]
for i in range(N, 0, -1):
    left_cal[i] = (v[i] + left_cal[i + 1] - x[i + 1] + x[i])

ans = 0
max_cal = []
for i in range(N + 1):
    max_cal.append(max(left_cal[i + 1 : ]) - x[i])
for i in range(N + 1):
    ans = max(ans, right_cal[i] + max_cal[i])
    
max_cal = [max(right_cal)]
for i in range(1, N + 1):
    max_cal.append(max(right_cal[ : i]) - C + x[i])
for i in range(N + 1):
    ans = max(ans, left_cal[i] + max_cal[i])
    
# print(right_cal)
# print(left_cal)
# print(max_cal)
print(ans)

### FIXED CODE ###

x = [0 for i in range(100001)]
v = [0 for i in range(100001)]
v_sum_right = [0 for i in range(100001)]
v_sum_left = [0 for i in range(100001)]
g = [[0, 0] for i in range(100001)]
g2= [0 for i in range(100001)]
N = 0
C = 0
i = 0
ans = 0
t = 0

N, C = [int(i) for i in input().split(" ")]
for i in range(N):
    x[i], v[i] = [int(i) for i in input().split(" ")]


v_sum_right[0] = v[0]
for i in range(1, N):
    v_sum_right[i] = v_sum_right[i - 1] + v[i]

v_sum_left[N] = 0
for i in range(N - 1, -1, -1):
    v_sum_left[i] = v_sum_left[i + 1] + v[i]


# // g計算
g[0][0] = 0
g[0][1] = 0
g2[0] = 0
for i in range(1, N + 1):
    g[i][0] = max(g[i - 1][0], v_sum_right[i - 1] - x[i - 1])
    g2[i] = max(g2[i - 1], v_sum_right[i - 1] - 2 * x[i - 1])
    if g[i - 1][0] == g[i][0]:
        g[i][1] = g[i - 1][1]
    else:
        g[i][1] = x[i - 1]
    
# // 探査
ans = v_sum_left[0] - C + x[0]
for i in range(1, N):
    ans = max(ans, v_sum_left[i] + g[i][0] - 2 * (C +- x[i]), v_sum_left[i] - C + x[i] + g2[i])
ans = max(ans, g[N][0])

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

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

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

ans = 0

for i in range(N):
  for j in range(S+1):
    #from 0
    if j == 0: #j==0
      dp[i+1][j][0] += dp[i][j][0]
    if j+A[i] <= S and j == 0: #j==0
      dp[i+1][j+A[i]][1] = (dp[i+1][j+A[i]][1]+dp[i][j][0] * (i+1))%MOD
      dp[i+1][j+A[i]][2] = (dp[i+1][j+A[i]][2]+dp[i][j][0] * (i+1) * (N-i))%MOD
    #from 1
    dp[i+1][j][1] = (dp[i+1][j][1]+dp[i][j][1])%MOD
    if j+A[i] <= S:
      dp[i+1][j+A[i]][1] = (dp[i+1][j+A[i]][1]+dp[i][j][1])%MOD
      dp[i+1][j+A[i]][2] = (dp[i+1][j+A[i]][2]+dp[i][j][1] * (N-i))%MOD
    #from 2
    dp[i+1][j][2] = (dp[i+1][j][2]+dp[i][j][2])%MOD
#print(dp)MODDD
print(dp[N][S][2]%MOD)
      

### FIXED CODE ###

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

Q = [0 for _ in range(S+1)]
ans = 0
for i in range(N):
  Q[0] += 1
  Q2 = [0 for _ in range(S+1)]
  for j in range(S+1):
    Q2[j] += Q[j]%MOD
    if j+A[i] <= S: #(1+x^A[i])をかけてもx^sを超えないときに限り。
      Q2[j+A[i]] += Q[j]%MOD
  Q = Q2
  ans += Q[S]%MOD
ans = ans %MOD
print(ans)
### BUGGY CODE ###

import math

a, b = map(int, input().split())

def cf(x1,x2):
    cf=[]
    for i in range(1, min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

cf = cf(a, b)
counter = 0
for i in cf:
    if is_prime(i) or i == 1:
        counter += 1
print(counter)

### FIXED CODE ###

import math

a, b = map(int, input().split())

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)

    divisors.sort()
    return divisors

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

divisors_a = set(make_divisors(a))
divisors_b = set(make_divisors(b))

common_divisors = []
for a in divisors_a:
    if a in divisors_b:
        common_divisors.append(a)

counter = 0
for i in common_divisors:
    if is_prime(i) or i == 1:
        counter += 1
print(counter)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
maxsum = 0
for i in range(n-k+1):
	cnt = sum(p[i:i+k])
	if cnt >= maxsum:
		maxsum = cnt
print((maxsum+k)/2)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
u = sum(p[0:k])
maxsum = u
for i in range(1, n-k+1):
	u = u + p[i+k-1] - p[i-1]
	if u >= maxsum:
		maxsum = u
print((maxsum+k)/2)
### BUGGY CODE ###

s=input()
K=int(input())

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

### FIXED CODE ###

s=input()
K=int(input())

N=len(s)
S=set()
for i in range(N):
    for j in range(i+1,min(i+6,N+1)):
        S.add(s[i:j])
l=sorted(list(S))
print(l[K-1])