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

import sys
sys.setrecursionlimit(1000000)
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

rest = K
ans = 0

def dfs(cost, aindex, bindex, score):

    if K == cost:
        # print("1:", score, cost)
        return score
    elif K < cost:
        # print("2:", score, cost)
        return score - 1
    
    if aindex == N and bindex == M:
        # print("3:", score, cost)
        return score

    elif aindex >= N:
        return dfs(cost + B[bindex], aindex, bindex+1, score + 1)
    
    elif bindex >= M:
        return dfs(cost + A[aindex], aindex+1, bindex, score + 1)

    else:
        return max(dfs(cost + A[aindex], aindex+1, bindex, score + 1), dfs(cost + B[bindex], aindex, bindex + 1, score + 1))

print(max(dfs(A[0], 1, 0, 1), dfs(B[0], 0, 1, 1)))

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a, b = [0], [0]
for ai in A:
    a.append(a[-1] + ai)

for bi in B:
    b.append(b[-1] + bi)

# print(a, b)
ans = 0
bs = M
for i in range(N+1):
    if a[i] > K:
        break
    for j in reversed(range(bs+1)):
        if a[i] + b[j] <= K:
            ans = max(ans, i + j)
            bs = j
            break

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

import numpy as np


def resolve():
    N = int(input())
    d = [int(i) for i in input().split()]
    d = np.array(d)
    d = np.sort(d)
    count = 0
    for i in range(100000):
        if (np.nonzero(d >= i)[0].size == np.nonzero(d < i)[0].size):
            count += 1
    print(count)
    
resolve()

### FIXED CODE ###

import numpy as np
def resolve():
    N = int(input())
    d = [int(i) for i in input().split()]
    d = np.array(d)
    d = np.sort(d)
    print(d[N // 2] - d[N // 2 - 1])
resolve()
### BUGGY CODE ###

n = int(input())
nd = list(map(int, input().split()))
c = 0
for i in range(n):
    m = min(nd)
    index = nd.index(m)
    nd.remove(m)
    c += index
print(c)


### FIXED CODE ###

n = int(input())
nlist = list(map(int, input().split()))
W = [0for i in range(n)]
def M(l,r):      ##l~r-1 까지의 리스트.
    if (l+1 >= r):
        return 0
    elif (l+2 == r):
        if (nlist[l] <= nlist[l+1]):
            return 0
        else:
            nlist[l],nlist[l+1] = nlist[l+1],nlist[l]
            return 1
    ##위의 if문으로 (r-l)가 2이하일 경우는 해놓음
    m = (l+r)//2
    i = l
    j = m
    k = l
    cl = M(l,m)
    cr = M(m,r)
    c = 0
    while (i<m and j<r):
        if (nlist[i] <= nlist[j]):
            W[k] = nlist[i] ##l부터 r까지 W에 크기순으로 대입해나감
            k += 1
            i += 1
        else:
            W[k] = nlist[j]  ##일단 W[k]에는 더 작은쪽을 저장하는듯
            k += 1
            j += 1
            c += (m-i)  ##만약 nlist[i] > nlist[j]라면 i~m-1 까지 반전 하고있기 때문
                        ##그러고 더 작은 nlist[j]를 안에 넣는것.
    while (i<m):   ##i번째쪽에 더 큰것들이 남았을 경우 (j=r 이 되있는 상황이기에 더 반전수를 늘리지는 않음)
        W[k] = nlist[i]
        k += 1
        i += 1
    while (j<r):   ##j쪽에 큰게 남아있는경우도 동일
        W[k] = nlist[j]
        k += 1
        j += 1
    for i in range(l,r): 
        nlist[i] = W[i]
    return cl+cr+c
        
print(M(0,n))
### BUGGY CODE ###

import math

n = int(input())
cell = map(lambda x: {"B": True, "W": False}[x], input())
section = 0
ans = 1
for val in cell:
    if section % 2 == 0:
        buf = val
    else:
        buf = not val
    if buf:
        section += 1
    else:
        ans *= section
        section -= 1
if section == 0:
    print(((math.factorial(n) % (10 ** 9 + 7)) * (ans % (10 ** 9 + 7))) % (10 ** 9 + 7))
else:
    print(0)

### FIXED CODE ###

import math

n = int(input())
cell = map(lambda x: {"B": True, "W": False}[x], input())
section = 0
ans = 1
for val in cell:
    if section % 2 == 0:
        buf = val
    else:
        buf = not val
    if buf:
        section += 1
    else:
        ans *= section
        ans %= 10 ** 9 + 7
        section -= 1
if section == 0:
    print(((math.factorial(n) % (10 ** 9 + 7)) * ans) % (10 ** 9 + 7))
else:
    print(0)
### BUGGY CODE ###

x,y = map(int,input().split())

for i in range(1, 10**9):
    if x * i % y != 0:
        print(x*i)
        break
    if x*i >= 10**18:
        print(-1)
        break

### FIXED CODE ###

x,y = map(int,input().split())

for i in range(1, 10**9):
    if x * i % y != 0:
        print(x*i)
        break
    if x*i <= 10**18:
        print(-1)
        break
### BUGGY CODE ###

import heapq

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] <= reached[h][w]:
                continue
            reached[nh][nw] = reached[h][w]
            heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] <= reached[h][w] + cost:
                    continue
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

N, A, B = input().split()
N = int(N)
A = int(A)
B = int(B)

L = []
i = 0
k = 0
j = 0

for k in range(10**18):
    for i in range(A):
        L.append('b')
        if len(L) >= N:
            L = L[0:N]
            print(L.count('b'))
            exit()
    
    for j in range(B):
        L.append('r')
        if len(L) >= N:
            L = L[0:N]
            print(L.count('b'))
            exit()

### FIXED CODE ###

N, A, B = map(int , input().split())
 
L = []
i = 0
k = 0
j = 0
P = N // (A + B)
Q = N % (A + B)

if A > Q:
    print((P * A) + Q)
else:
    print((P * A) + A)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(1, 10**5-2):
    if ans < A.count(i) + A.count(i+1) + A.count(i+2):
        ans = A.count(i) + A.count(i+1) + A.count(i+2)
print(ans)

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    count = [0] * 10 ** 5
    for i in A:
        if i > 1:
            count[i - 1] += 1
        count[i] += 1
        if i < 10**5-1:
            count[i + 1] += 1
    print(max(count))
resolve()
### BUGGY CODE ###

n = int(input())
S = input()
cnt=0
for i in range(1000):
    x = str(i).zfill(3)
    k=0
    j=0
    while j<3 and k<n:
        if x[j] in S[k]:
            if j==2:
                cnt+=1
                break
            else:
                j+=1
                k+=1
        else:
            k+=1
print(cnt)

### FIXED CODE ###

n = int(input())
S = input()
cnt=0
for i in range(10):
    x=S.find(str(i),0,n-2)
    if x!=-1:
        for j in range(10):
            y=S.find(str(j),x+1,n-1)
            if y!=-1:
                for k in range(10):
                    z=S.find(str(k),y+1,n)
                    if z!=-1:
                        cnt+=1
print(cnt)
### BUGGY CODE ###

N = int(input())
nums = list(map(int,input().split()))
x = [0] * N
ans = 0
for i in range(N):
    x[nums[i] - 1] += 1
for u in  range(N):
    x[nums[u] - 1] -= 1
    for i in range(N):
        ans += (x[i]*(x[i]-1))/2
    print(int(ans))
    x[nums[u] - 1] += 1
    ans = 0

### FIXED CODE ###

N = int(input())
nums = list(map(int,input().split()))
x = [0] * N
ans = 0
for i in range(N):
    x[nums[i] - 1] += 1
for i in range(N):
    ans += (x[i]*(x[i]-1))/2
ans = int(ans)    
for i in range(N):
    if x[nums[i] - 1] == 0 or x[nums[i] - 1] ==1:
        print(ans)
    else:
        print(ans - x[nums[i]-1] + 1)
### BUGGY CODE ###

import numpy as np 

H,W = map(int,input().split())
S = np.array(
    list(map(lambda x:list(map(
        lambda x:[0,1][x == "."],list(input())
    )),range(H)
)))

funcA = np.frompyfunc(lambda x,y:y and x+y,2,1)
funcB = np.frompyfunc(lambda x,y:[y,x][(y and x and 1)],2,1)
Hor = funcA.accumulate(S,dtype=np.object,axis=1).astype(np.int)[:,::-1]
Hor = funcB.accumulate(Hor,dtype=np.object,axis=1).astype(np.int)[:,::-1]
Ver = funcA.accumulate(S,dtype=np.object,axis=0).astype(np.int)[::-1,:]
Ver = funcB.accumulate(Ver,dtype=np.object,axis=0).astype(np.int)[::-1,:]
print(np.max(Hor+Ver-1))

### FIXED CODE ###

H,W = map(int,input().split())
S = [0]*H
for i in range(H):
    S[i] = list(input())

def aaa(s):
    i = 0
    l = len(s)
    o = []
    while True:
        if i == l:
            break
        if s[i] == ".":
            n = 0
            while i < l and s[i] == '.':
                i += 1
                n += 1
            o += [n] * n
        else:
            o += [0]
            i += 1
    return o

Hor = [0]*H
y = 0
while y != H:
    Hor[y] = aaa(S[y])
    y += 1

Ver = [0]*W
x = 0
while x != W:
    _ = 0
    s = [0] * H
    while _ != H:
        s[_] = S[_][x]
        _ += 1
    Ver[x] = aaa(s)
    x += 1

ans = 1
x = 0
while x != W:
    y = 0
    while y != H:
        h = Hor[y][x]
        if h:
            v = Ver[x][y]
            ans = max(ans,h+v-1)
        y += 1
    x += 1

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

def main():
  AC = 0
  WA = 0
  
  solving = {}
  solved = []
  
  N,M = map(int, input().split())
  
  Q = [] 
  
  P = [0] * M
  S = [0] * M
  
  for i in range(M):
    p, s = input().split()
    if p in solved:
      continue
    elif s == 'WA':
      if p not in solved:
        if p in solving:
          _wa = solving[p]
          solving[p] = _wa + 1
        else:
          solving[p] = 1
    else:
      AC += 1
      if p in solving:
      	WA += solving[p]
      solved.append(p)
  
  print(AC, WA)
  return 0

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  AC = 0
  WA = 0
  
  solving = {}
  solved = {}
  
  N,M = map(int, input().split())
  
  for i in range(M):
    p, s = input().split()
    if p in solved:
      continue
    elif s == 'WA':
      if p in solving:
        _wa = solving[p]
        solving[p] = _wa + 1
      else:
        solving[p] = 1
    else:
      AC += 1
      if p in solving:
      	WA += solving[p]
      solved[p] = True
  
  print(AC, WA)
  return 0
 
if __name__ == "__main__":
  main()
### BUGGY CODE ###

n, m = list(map(int, input().rstrip().split(" ")))
friend_mat = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
  friend_mat[i][i] = 1
for mm in range(m):
  a, b = list(map(int, input().rstrip().split(" ")))
  if not friend_mat[a-1][b-1]:
    friend_mat[a-1][b-1] = 1
    friend_mat[b-1][a-1] = 1
print(max([sum(friend_mat[i]) for i in range(n)]))

### FIXED CODE ###

def root(x, root_ls):
  if root_ls[x] < 0:
    return x
  else:
    root_ls[x] = root(root_ls[x], root_ls)
    return root_ls[x]

def unite(a, b, root_ls):
  a = root(a, root_ls)
  b = root(b, root_ls)
  if a != b:
    root_ls[a] += root_ls[b]
    root_ls[b] = a
  
n, m = list(map(int, input().rstrip().split(" ")))
members = [-1 for i in range(n)]
max_idx = 0
for mm in range(m):
  a, b = list(map(int, input().rstrip().split(" ")))
  unite(a-1, b-1, members)
print(max([-m for m in members]))
### BUGGY CODE ###

from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

X, Y, Z, K = list(map(int, input().split()))
A = list(sorted(map(int, input().split()), reverse=True))
B = list(sorted(map(int, input().split()), reverse=True))
C = list(sorted(map(int, input().split()), reverse=True))

heap = []
heapq.heappush(heap, (-(A[0] + B[0] + C[0]), 0, 0, 0))
history = set()
while len(history) < K:
    d, a, b, c = heapq.heappop(heap)
    if a + 1 < X:
        heapq.heappush(heap, (-(A[a + 1] + B[b] + C[c]), a + 1, b, c))
    if b + 1 < Y:
        heapq.heappush(heap, (-(A[a] + B[b + 1] + C[c]), a, b + 1, c))
    if c + 1 < Z:
        heapq.heappush(heap, (-(A[a] + B[b] + C[c + 1]), a, b, c + 1))
    if (a, b, c) not in history:
        history.add((a, b, c))
        print(-d)


### FIXED CODE ###

import heapq

x, y, z, k = map(int, input().split())
ali = list(reversed(sorted(map(int, input().split()))))
bli = list(reversed(sorted(map(int, input().split()))))
cli = list(reversed(sorted(map(int, input().split()))))

done = {}
count = 0

heap = []


def main(a, b, c):
    global count
    if '{}'.format((a, b, c)) in done:
        return
    done['{}'.format((a, b, c))] = True
    count += 1
    print(ali[a] + bli[b] + cli[c])
    if a + 1 < x:
        heapq.heappush(heap, (-(ali[a + 1] + bli[b] + cli[c]), a + 1, b, c))
    if b + 1 < y:
        heapq.heappush(heap, (-(ali[a] + bli[b + 1] + cli[c]), a, b + 1, c))
    if c + 1 < z:
        heapq.heappush(heap, (-(ali[a] + bli[b] + cli[c + 1]), a, b, c + 1))


main(0, 0, 0)
while count < k:
    s, a, b, c = heapq.heappop(heap)
    main(a, b, c)
### BUGGY CODE ###

n = int(input())
s=[]
s#+=['a']
#s+=['b']
#print(s)
c = 0
ans = 1
for i in range(n):
    s += [input()]
for i in range(1,n):
    for j in range(i):
        if s[i] == s[j]:
            c += 1
    if c == 0:
        ans += 1
    c = 0
print(ans)

### FIXED CODE ###

n = int(input())
s=[]
ans = 1
for i in range(n):
    s += [input()]
s.sort()
for i in range(n-1):
    if s[i] != s[i+1]:
        ans += 1
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
h,w = [int(i) for i in readline().split()]

a = [[int(i) for i in readline().split()] for _ in range(h)]
b = [[int(i) for i in readline().split()] for _ in range(h)]


dp = [set() for _ in range(w)]
dp[0] = set([0])

#print(dp)
for i in range(h):
    ndp = [set() for _ in range(w)]
    for j in range(w):
        v = abs(a[i][j] - b[i][j])
        #print(v)
        s1 = set(c+v for c in dp[j] if c+v <= 6400)
        s2 = set(abs(c-v) for c in dp[j] if c >= v)
        if j:
            s3 = set(c+v for c in ndp[j-1] if c+v <= 6400)
            s4 = set(abs(c-v) for c in ndp[j-1])
            ndp[j] = s1|s2|s3|s4
        else:
            ndp[j] = s1|s2
            
    dp = ndp
    #print(dp)
    

print(min(dp[j]))














### FIXED CODE ###


# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
h,w = [int(i) for i in readline().split()]

a = [[int(i) for i in readline().split()] for _ in range(h)]
b = [[int(i) for i in readline().split()] for _ in range(h)]


dp = [[0] for _ in range(w)]
dp[0][0] = 1

#print(dp)
N = 6401
for i in range(h):
    ndp = [[0]*N for _ in range(w)]
    for j in range(w):
        v = abs(a[i][j] - b[i][j])
        #print(v)
        for ii,c in enumerate(dp[j]):
            if ii+v < N:
                ndp[j][abs(ii+v)] |= c
            ndp[j][abs(ii-v)] |= c
        if j:
            for ii,c in enumerate(ndp[j-1]):
                if ii+v < N:
                    ndp[j][abs(ii+v)] |= c
                ndp[j][abs(ii-v)] |= c

    dp = ndp
    #print(dp)
    
c = [i for i,c in enumerate(dp[j]) if c]

#print(c)
print(min(c))
### BUGGY CODE ###

N = int(input())
S = input()

cnt = 0
for i in range(N-2):
    for j in range(i,N):
        if S[i] == S[j]:
            continue
        for k in range(j,N):
            if S[i] == S[k] or S[j] == S[k]:
                continue
            if j-i == k-j:
                continue
            cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
S = input()

# 組み合わせ総数
ans = S.count('R') * S.count('G') * S.count('B')

for i in range(N):
    for j in range(i+1,N):
        k = 2 * j - i
        if k >= N:
            break
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

import numpy as np
from collections import Counter


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

s = np.array(sorted(set(a)),int)
bl = np.array([True]*len(s), bool)
for i in range(1, len(s)):
    mod = s[i]
    buf = s[:i][bl[:i]]
    for j in range(len(buf)):
        if mod % buf[j] == 0:
            bl[i] = False
            break
s = set(s[bl])

c = Counter(a)
keys = set([k for k, v in c.items() if v == 1])

print(len(s&keys))

### FIXED CODE ###

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

a.sort()
a_max = a[-1] + 1   # aの最大値
lst = [0] * a_max   # a_max個のリストを生成

for x in a:
    lst[x] += 1                         # リストの該当の数字に1追加 
    if lst[x] == 1:                     # まだ他の数値の倍数でなければ、リストへ2倍、3倍…の数字を1追加していく
        for i in range(x*2, a_max, x):
            lst[i] += 1

output = 0
for x in a:
    if lst[x] == 1:
        output += 1
print(output)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [0] + list(map(int, input().split()))

dp = [float("inf") for _ in range(N + 1)]
dp[1] = 0

for i in range(1, N + 1):
    for j in range(i + 1, min(i + K + 1, N + 1)):
        dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))

print(dp[N])


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    h = [0] + list(map(int, input().split()))
    dp = [float("inf") for _ in range(N + 1)]

    dp[1] = 0
    for i in range(2, N + 1):
        dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i - K), i))

    print(dp[-1])


main()
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]

ans = []
for k in reversed(range(1, N + 1)):
    t = N // k
    cnt = 0
    for i in range(1, t + 1):
        if i * k in ans:
            cnt += 1
    if cnt % 2 != a[k - 1]:
        ans.append(k)

x = len(ans)
print(x)
if x >= 0:
    print(*ans)


### FIXED CODE ###

from sys import stdin

N = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]

ans = []
for k in reversed(range(1, N + 1)):
    if a[k - 1] == 1:
        ans.append(k)
        tmp = 1
        while tmp * tmp <= k:
            if k % tmp == 0:
                a[tmp - 1] ^= 1
                if tmp != k // tmp:
                    a[k // tmp - 1] ^= 1
            tmp += 1

x = len(ans)
print(x)
if x >= 0:
    print(*ans)
### BUGGY CODE ###

N = int(input())
S = [sorted(list(input())) for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i]==S[j]:
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = [''.join(sorted(input())) for _ in range(N)]

D = {}
ans = 0
for s in S:
    if s in D:
        D[s] += 1
        ans += D[s]
    else:
        D[s] = 0

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

n = int(input())
ans = 0
for i in range(1,n):
    for j in range(1,n):
        if i*j <= n-1:
            ans += 1
        else:
            break
print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n):
    for j in range(i,n):
        if i*j <= n-1:
            if i == j:
                ans += 1
            else:
                ans += 2
        else:
            break
print(ans)
### BUGGY CODE ###

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

#まだ左端を選択していない状態(状態 0)。この時は和が0の時1通りでそれ以外は0。
#左端は選択済みだけど右端は選択していない状態(状態 1)
#右端も選択済みの状態(状態 2)

dp = [[[0 for _ in range(3)] for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
#i個目までで和がjとなる場合の数
ans = 0

for i in range(N):
  for j in range(S+1):
    #from 0
    if j == 0: #j==0の時以外は基本0なのであってもなくても良い。
      dp[i+1][j][0] += dp[i][j][0]%MOD
    if j+A[i] <= S and j == 0: #j==0の時以外は基本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][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

def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
a_reverse = a.copy()[::-1]

plus = 0
cnt = 0
ind = 0
ceil = nCr(n, k)
while cnt < ceil:
    kaisu = nCr(n-(ind+1), k-1)
    cnt += kaisu
    plus = plus + kaisu * a_reverse[ind]
    ind += 1

minus = 0
cnt = 0
ind = 0
while cnt < ceil:
    kaisu = nCr(n-(ind+1), k-1)
    cnt += kaisu
    minus = minus + kaisu * a[ind]
    ind += 1

print((plus-minus) % mod)

### FIXED CODE ###

n,k = map(int, input().split())
a = sorted(list(map(int, input().split())))
a_reverse = a[::-1]
mod = 10**9+7
 
factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))
 
def comb(n, r, mod):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod

plus = 0
minus = 0
cnt = 0
ind = 0
for i in range(n-k+1):
    kaisu = comb(n-i-1, k-1, mod)
    plus = (plus + (kaisu * a_reverse[ind]) % mod) % mod
    minus = (minus + (kaisu * a[ind]) % mod) % mod
    ind += 1

print((plus-minus) % mod)