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

import sys
sys.setrecursionlimit(1000000000)

n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0

c = 1
nCk = [1]
for r in range(k,n+1):
    c_ = c*r//(r-k+1)
    c = c_
    nCk.append(c_)

if k == 1:
  print(0)
else:
  for i in range(1,n+1):
    if n-i < k-1:
      break
    ans += (a[n-i]-a[i-1])*nCk[n-i-k+1]
  print(ans%1000000007)

### FIXED CODE ###

n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0

from operator import mul
from functools import reduce
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5
fact = [1, 1]  
factinv = [1, 1]
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

if k == 1:
  print(0)
else:
  for i in range(1,n):
    if n-i < k-1:
      break
    ans += a[n-i]*cmb(n-i,k-1,p)
    ans -= a[i-1]*cmb(n-i,k-1,p)
  print(ans%1000000007)
### BUGGY CODE ###

h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]


dp=[[set() for j in range(w)]for i in range(h)]
sub=a[0][0]-b[0][0]
dp[0][0].add(sub)
dp[0][0].add(-sub)

for c in range(h):
    for l in range(w):
        sub=a[c][l]-b[c][l]
        if c!=0:
            for p in dp[c-1][l]:
                dp[c][l].add(p+sub)
                dp[c][l].add(p-sub)
        if l!=0:
            for p in dp[c][l-1]:
                dp[c][l].add(p+sub)
                dp[c][l].add(p-sub)
st=dp[-1][-1]
for i in range(1000000):
    if (i in st)or(-i in st):
        print(i)
        break

### FIXED CODE ###

h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]

pos = 160*80
dp=[[0]*w for i in range(h)]
sub=abs(a[0][0]-b[0][0])
dp[0][0]=1<<(pos-sub)
dp[0][0]=1<<(pos+sub)

for c in range(h):
    for l in range(w):
        sub=abs(a[c][l]-b[c][l])
        if l!=0:
            dp[c][l]|=dp[c][l-1]<<sub
            dp[c][l]|=dp[c][l-1]>>sub
        if c!=0:
            dp[c][l]|=dp[c-1][l]<<sub
            dp[c][l]|=dp[c-1][l]>>sub
bit=dp[-1][-1]
for i in range(pos):
    if (bit&1<<(pos+i))or(bit&1<<(pos-i)):
        print(i)
        break
### BUGGY CODE ###

N = int(input())
memory = []
counter = 0

for i in range(N):
    tmp = input()
    if tmp not in memory:
        counter += 1
        memory.append(tmp)

print(counter)

### FIXED CODE ###

import collections

N = int(input())
memory = []
counter = 0

for i in range(N):
    tmp = input()
    memory.append(tmp)

c = collections.Counter(memory)

print(len(c))
### BUGGY CODE ###

import sys

# sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    inf = 10 ** 20
    n = read_int()
    weight = {}
    adj = {u: [] for u in range(1, n + 1)}
    for i in range(n - 1):
        a, b, c = read_int_list()
        adj[a].append(b)
        adj[b].append(a)
        weight[(a, b)] = c
        weight[(b, a)] = c

    q, k = read_int_list()
    state = {u: 0 for u in range(1, n + 1)}
    d = {u: inf for u in range(1, n + 1)}

    state[k] = 1
    d[k] = 0
    Q = [k]
    while Q:
        u = Q.pop(0)
        for v in adj[u]:
            if state[v] == 0:
                state[v] = 1
                d[v] = d[u] + weight[(u, v)]
                Q.append(v)
        # state[u] = 2

    res = [0] * q
    for i in range(q):
        x, y = read_int_list()
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()


### FIXED CODE ###

import sys
from collections import deque


# sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    n = read_int()
    adj = [[] for u in range(n+1)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adj[a].append((b, c))
        adj[b].append((a, c))

    d = [0] * (n+1)
    q, k = read_int_list()

    # Q = [(k, 0, 0)]
    Q = deque([(k, 0, 0)])
    while Q:
        u, parent, dist = Q.popleft()
        for v, w in adj[u]:
            if v != parent:
                Q.append((v, u, dist+w))
        d[u] = dist

    res = [0] * q
    for i in range(q):
        x, y = map(int, input().split())
        res[i] = d[x] + d[y]
    print(*res, sep='\n')


main()
### BUGGY CODE ###

def hahaha():
    n=int(input())
    list=[]
    count=0
    flag=0
    for i in range(0,n):
        list.append(str(input()))
        flag=0
        for j in range(0,i):
            if list[i]==list[j]:
                flag=1
        if flag==0:
            count=count+1
    print(count)
if __name__ == '__main__':
    hahaha()


### FIXED CODE ###

def hahaha():
    n=int(input())
    count=1
    list=[]
    for i in range(0,n):
        list.append(str(input()))
    list.sort()
    a=list[0]
    for j in range(0,n):
        if a!=list[j]:
            a=list[j]
            count+=1
    print(count)
if __name__ == '__main__':
    hahaha()
### BUGGY CODE ###

def we_love_abc(S: str)->int:
    n = len(S)
    dp = [[0, 0, 0, 0] for _ in range(n + 1)]
    dp[n][3] = 1

    for i in range(n-1, -1, -1):
        dp[i][3] = (3 if S[i] == '?' else 1) * dp[i+1][3]
        for j in range(3):
            m1 = 3 if S[i] == '?' else 1
            m2 = 1 if S[i] == '?' or S[i] == 'ABC'[j] else 0
            dp[i][j] = m1 * dp[i+1][j] + m2 * dp[i+1][j+1]

    return dp[0][0] % (10**9 + 7)


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)


### FIXED CODE ###

def we_love_abc(S: str)->int:
    ABC = 'ABC'
    MOD = 1000000007

    dp = [0, 0, 0, 0]
    dp[3] = 1

    for c in reversed(S):
        for j in range(3):
            m1 = 3 if c == '?' else 1
            m2 = 1 if c == '?' or c == ABC[j] else 0
            dp[j] = (m1 * dp[j] + m2 * dp[j+1]) % MOD
        dp[3] = (3 if c == '?' else 1) * dp[3]
        dp[3] %= MOD

    return dp[0] % MOD


if __name__ == "__main__":
    S = input()
    ans = we_love_abc(S)
    print(ans)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
rgb = sorted([r,g,b])

ans=0
for i in range(n//rgb[2]+1):
    for j in range((n-i*rgb[2])//rgb[1]+1):
        d = n-i*rgb[2]-j*rgb[1]
        if d%rgb[0]==0 and d>=0:
            ans+=1

print(ans)

### FIXED CODE ###

rgb = [0]*3
rgb[0],rgb[1],rgb[2],n = map(int,input().split())
rgb.sort()

ans=0
for i in range(n//rgb[2]+1):
    for j in range((n-i*rgb[2])//rgb[1]+1):
        d = n-i*rgb[2]-j*rgb[1]
        if d%rgb[0]==0 and d>=0:
            ans+=1

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

n = int(input())
a = list(map(int, input().split()))
b = set()
c = [0]*n

for i in range(n):
  if a[n-1-i] ^ c[n-1-i]%2:
    b.add(n-i)
    for j in range(1, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        c[j-1] = c[j-1]^1
        if (n-i)//j != j:
          c[(n-i)//j -1] = c[(n-i)//j -1]^1

print(len(b))
if len(b)>0:
  print(*b)

### FIXED CODE ###

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

for i in range(n-1):
  if a[n-1-i]&1:
    b.add(n-i)
    for j in range(2, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        a[j-1] += 1
        if (n-i)//j != j:
          a[(n-i)//j -1] += 1
if a[0] != len(b)%2:
  b.add(1)
          
print(len(b))
if len(b)>0:
  print(*b)
### BUGGY CODE ###

n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)

# import numpy as np
ans=0
now=[]
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        now.append(b)
    #print(nouki, now)
    if now==[]:continue
    m=max(now)
    ans+= m
    now.remove(m)

print(ans)
    


### FIXED CODE ###

n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)

# import numpy as np
import bisect as bi
ans=0
now=[]
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        bi.insort(now,b)
    #print(nouki, now)
    if now==[]:continue
    ans+= now[-1]
    del now[-1]


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

N = int(input())
X = [[] for _ in range(N)]
ans = 0
for i in range(N):
    X[i] = list(map(int, input().split()))

for i in range(1, N):
    for j in range(i):
        ans = max(ans,(abs(X[i][0]-X[j][0])+abs(X[i][1]-X[j][1])))
print(ans)

### FIXED CODE ###

N = int(input())
X = [[] for _ in range(N)]
z = [0 for _ in range(N)]
w = [0 for _ in range(N)]
for i in range(N):
    X[i] = list(map(int, input().split()))
    z[i] = X[i][0] +X[i][1]
    w[i] = X[i][0] -X[i][1]

ans = max(max(z)-min(z), max(w)-min(w))
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range (0, N):
	if A[i] == 0:
		ans = 0
		break
	else:
		ans *= A[i]

if ans > 10 ** 18:
	print(-1)
else:
	print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range (0, N):
	if A[i] == 0:
		ans = 0
		break
	else:
		if ans > 0:
			ans *= A[i]
		if ans > 10 ** 18:
			ans = -1

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

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

count_i = 0
for i in range(0, N):
    for j in range(0, i):
        if sta[i] > sta[j]:
            count_i -= 1
            break
    count_i += 1

print(count_i)


### FIXED CODE ###

N = int(input())
sta = list(map(int, input().split()))
min_i = sta[0]
count_i = 0
for i in sta:
    if min_i > i:
        min_i = i
    if i <= min_i:
        count_i += 1

print(count_i)
### BUGGY CODE ###

N,K=map(int,input().split())
lh=list(map(int,input().split()))
ldp=[float("inf") for i in range(N)]
"""for i in range(K):
    if i<=N-1:
        ldp[i]="""
ldp[0]=0
for i in range(1,N):
    mintmp=float("inf")
    for j in range(1,K+1):
        if i-j>=0:
            mintmp=min(mintmp,ldp[i-j]+abs(lh[i]-lh[i-j]))
    ldp[i]=mintmp
#print(ldp)
print(mintmp)


### FIXED CODE ###

N,K=map(int,input().split())
lh=list(map(int,input().split()))
ldp=[float("inf") for i in range(N)]
"""for i in range(K):
    if i<=N-1:
        ldp[i]="""
ldp[0]=0
for i in range(1,N):
    mintmp=float("inf")
    for j in range(1,K+1):
        if i-j>=0:
            mintmp=min(mintmp,ldp[i-j]+abs(lh[i]-lh[i-j]))
    ldp[i]=mintmp
#print(ldp)
print(mintmp)
### BUGGY CODE ###

import sys
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = 1000000007

if n >= 3:
    if 1 not in a  and 2 not in a:
        c = [1,2]
    elif 1 in a and 2 not in a:
        c = [0,1]
    elif 1 not in a and 2 in a:
        c = [1,0]
    else:
        c = [0,0]

    for i in range(2,n):
        if i+1 in a:
            c.append(0)
        else:
            c.append((c[i-2] + c[i-1])%mod)

    print(c[len(c)-1])
    sys.exit()
elif n == 2:
    if 1 not in a  and 2 not in a:
        c = [1,2]
    elif 1 in a and 2 not in a:
        c = [0,1]
    elif 1 not in a and 2 in a:
        c = [1,0]
    else:
        c = [0,0]

    print(c[1])
    sys.exit()
elif n == 1:
    if 1 in a:
        print(0)
        sys.exit()
    else:
        print(1)
        sys.exit()

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
inf = float("inf")
dp = [0] * (N+1)
for i in A:
	dp[i] = inf
dp[0] = 1
if dp[1] != inf:
	dp[1] = 1
for i in range(2,N+1):
	if dp[i] == inf:
		continue

	a = dp[i-2] if dp[i-2] != inf else 0
	b = dp[i-1] if dp[i-1] != inf else 0

	dp[i] = (a + b) % 1000000007


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

def main():
    n, m = map(int, input().split())
    a = []
    c = []
    for i in range(m):
        sa, sb = map(int, input().split())
        sc = list(map(int, input().split()))
        tc = 0
        a.append(sa)
        for j in sc:
            tc += 2 ** (j - 1)
        c.append(tc)

    dp = [10 ** 7 for j in range(2 ** n)]
    dp[0] = 0
    for i in range(m):
        sc = c[i]
        for j in range(2 ** n):
            dp[int(j | sc)] = min(dp[int(j | sc)], dp[j] + a[i])

    if dp[2 ** n - 1] == 10 ** 7:
        print(-1)
    else:
        print(dp[2 ** n - 1])


main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    a = []
    c = []
    dp = [10 ** 7 for j in range(2 ** n)]
    dp[0] = 0
    for _ in range(m):
        a, b = map(int, input().split())
        sc = list(map(int, input().split()))
        c = 0
        for j in sc:
            c += 2 ** (j - 1)
        for j in range(2 ** n):
            dp[j | c] = min(dp[j | c], dp[j] + a)

    if dp[2 ** n - 1] == 10 ** 7:
        print(-1)
    else:
        print(dp[2 ** n - 1])


main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

N,S, *A = map(int, sys.stdin.buffer.read().split())
mod = 998244353

answer = [0 for _ in range(S+1)]
power2 = 1

for j in range(N):
  a = A[j]
  answer_next = [2*answer[i] for i in range(S+1)]
  for i in range(a+1,S+1):
    answer_next[i] += answer[i-a]
  if a<=S:
    answer_next[a] += power2
  power2 = (2*power2)%mod
  answer = [answer_next[i]%mod for i in range(S+1)]

print(answer[S])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N,S, *A = map(int, sys.stdin.buffer.read().split())
mod = 998244353

answer = [0 for _ in range(S+1)]
power2 = 1

for a in A:
  answer_next = [(2*b)%mod for b in answer]
  if a<=S:
    answer_next[a] = (answer_next[a]+power2)%mod
    for i in range(a+1,S+1):
      answer_next[i] = (answer_next[i]+answer[i-a])%mod
  answer = answer_next
  power2 = (2*power2)%mod

print(answer[S])
### BUGGY CODE ###

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

w = []
v = []

for i in range(N):
	a,b = map(int,input().split())
	w.append(a)
	v.append(b)

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
	for sum_w in range(W+1):
		if sum_w - w[i] >=0:
			dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])

		dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])


### FIXED CODE ###

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

w = []
v = []

for i in range(N):
	a,b = map(int,input().split())
	w.append(a)
	v.append(b)

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
	for sum_w in range(W+1):
		if sum_w - w[i] >=0:
			dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])

		dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())
    tmp = []
    for i in range(q):
        tmp.append(input().split())

    for t in tmp:
        if len(t) == 1:
            s = s[::-1]
        else:
            f = int(t[1])
            c = t[2]
            if f == 1:
                s = c + s
            else:
                s = s + c

    print(s)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque

def main():
    input = sys.stdin.readline

    s = input()[:-1]
    q = int(input())
    tmp = [input().split() for _ in range(q)]

    flag = 0
    ans = deque([s])
    for t in tmp:
        if len(t) == 1:
            flag = ~flag 
        else:
            f = int(t[1])
            c = t[2]
            if (f == 1 and flag == 0) or (f ==2 and flag == -1):
                ans.appendleft(c)
            else:
                ans.append(c)
    if flag == 0:
        print(''.join(ans))
    else:
        print(''.join(ans)[::-1])

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

n,k = map(int,input().split())
A = sorted(list(map(int,input().split())))
F = sorted(list(map(int,input().split())))[::-1]
o = []
for a,f in zip(A,F):
    o.append(a*f)
ok = max(o)    
ng = -1

while ok - ng > 1:
    mid = (ok+ng)//2
    k1 = 0
    for i in range(n):
        k1 += max( 0 , A[i]- mid//F[i])
    if k1<= k:
        ok = mid
    else:
        ng = mid
print(ok)


### FIXED CODE ###

n,k = map(int,input().split())
A = sorted(list(map(int,input().split())))
F = sorted(list(map(int,input().split())))[::-1]
o = []
for a,f in zip(A,F):
    o.append(a*f)
ok = max(o)    
ng = -1

while ok - ng > 1:
    mid = (ok+ng)//2
    k1 = 0
    for i in range(n):
        k1 += max( 0 , A[i]- mid//F[i])
    if k1<= k:
        ok = mid
    else:
        ng = mid
print(ok)
### BUGGY CODE ###

from collections import deque

S = list(input())
Q = int(input())

for _ in range(Q):
  item = list(input().split())
  if item[0] == '1':
    S.reverse()

  else:
    if item[1] == '1':
      S_deque = deque(S)
      S_deque.appendleft(item[2])
      S = list(S_deque)

    else:
      S.append(item[2])

print(''.join(S))

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

S_deque = list(input())
S_deque = deque(S_deque[:-1])
Q = int(input())

top_flag = 1 # 0なら末尾、1なら最初

for _ in range(Q):
  item = list(input().split())
  if item[0] == '1':
    if top_flag == 0:
      top_flag = 1
    else:
      top_flag = 0

  else:
    in_flag = top_flag + int(item[1])
    if in_flag % 2 == 0:
      S_deque.appendleft(item[2])
    else:
      S_deque.append(item[2])

if top_flag == 0:
  S_deque.reverse()
else:
  pass

print(''.join(S_deque))
### BUGGY CODE ###

N=int(input())
count=0
if N<357:
    print(count)
else:
    for i in range(357,N+1):
        a=[0,0,0]#3,5,7の個数
        s=str(i)#文字列に直す
        for j in range(len(s)):# iの各桁の探索
            if s[j]=='3':
                a[0]+=1
            elif s[j]=='5':
                a[1]+=1
            elif s[j]=='7':
                a[2]+=1
            else:
                break
        b=a[0]+a[1]+a[2]#3,5,7の個数
        if a[0]>0 and a[1]>0 and a[2]>0 and b==len(s):
            count+=1
    print(count)

### FIXED CODE ###

N=int(input())

def dfs(s):
    if int(s)>N:
        return 0
    ret=1 if all (s.count(c)>0 for c in '753') else 0
    for c in '753':
        ret+=dfs(s+c)
    return ret

print(dfs('0'))
### BUGGY CODE ###

N, H = list(map(int, input().split()))
a = []
b = []
for i in range(N):
    temp0, temp1 = list(map(int, input().split()))
    a.append(temp0)
    b.append(temp1)

b_temp = []
for i in b:
    if max(a) <= i:
        b_temp.append(i)
b = b_temp
if H <= sum(b):
    b.sort()
    b.reverse()
    for i, throw in enumerate(b):
        H -= throw
        if H <= 0:
            result = i + 1
            break
else:
    if len(b) != 0:
        H -= sum(b)
    dev = int(H / max(a))
    if H % max(a) != 0:
        dev += 1
    result = len(b) + dev

print(result)


### FIXED CODE ###

import numpy as np

N, H = list(map(int, input().split()))
a = []
b = []
for i in range(N):
    temp0, temp1 = list(map(int, input().split()))
    a.append(temp0)
    b.append(temp1)

b = np.array(b)
b = b[max(a) < b]
# b_temp = []
# for i in b:
#     if max(a) <= i:
#         b_temp.append(i)
# b = b_temp
if H <= sum(b):
    # b.sort()
    b = np.sort(b)
    for i in range(len(b)):
        H -= b[-1 - i]
        if H <= 0:
            result = i + 1
            break
else:
    if len(b) != 0:
        H -= sum(b)
    dev = int(H / max(a))
    if H % max(a) != 0:
        dev += 1
    result = len(b) + dev

print(result)
### BUGGY CODE ###

from collections import defaultdict
from itertools import combinations_with_replacement
import sys
sys.setrecursionlimit(10 ** 9)

mod = 998244353

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

bin = [1]
for _ in range(n - 1):
    bin.append((bin[-1] * 2) % mod)
    
lst = []

zero = 0
for num in a:
    if num > s:
        continue
    if num == s:
        zero += 1
        continue
    lst.append(num % s)
lst.sort()
ans = (zero * bin[-1]) % mod
length = len(lst)

def knapsack(pos, total, num):
    global ans
    if total == s:
        ans = (ans + bin[-num]) % mod
        return
    if pos == length:
        return
    if total + lst[pos] <= s:
        knapsack(pos + 1, total + lst[pos], num + 1)
        knapsack(pos + 1, total, num)

knapsack(0, 0, 0)
print(ans)


### FIXED CODE ###

mod = 998244353

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] = 1
for i, num in enumerate(a, start = 1):
    for j in range(s + 1):
        dp[i][j] = (dp[i - 1][j] * 2) % mod
        if j - num >= 0:
            dp[i][j] += dp[i - 1][j - num]

print(dp[-1][-1] % mod)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
dic={}
for i in range(len(A)):
  if A[i] in dic:
    dic[A[i]]+=1
  else:
    dic[A[i]]=1    
def ans(k,dic):
  dic[A[k-1]]+=-1
  c=0
  for i in dic.values():
    c+=i*(i-1)/2
  dic[A[k-1]]+=1  
  return int(c)
for k in range(1,N+1):
  print(ans(k,dic))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
dic={}
for a in A:
  if a in dic:
    dic[a]+=1
  else:
    dic[a]=1
   

c=0
for i in dic.values():
  c+=i*(i-1)/2
for j in range(1,N+1):
  d=c-dic[A[j-1]]+1
  print(int(d))
### BUGGY CODE ###

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

# スペース区切りの整数の入力
h, w, m = map(int, input().split())

h_list = [0]*h
w_list = [0]*w

# print(h_list)
# print(w_list)

h_w_list = [[0 for j in range(w)] for i in range(h)]
# print(h_w_list)


for zzz in range(m):
  # print("---")
  bom_h, bom_w = map(int, input().split())
  # print(bom_h, bom_w)
  h_list[bom_h-1] = h_list[bom_h-1] + 1
  w_list[bom_w-1] = w_list[bom_w-1] + 1

  h_w_list[bom_h-1][bom_w-1] = "target"

  # print(h_list)
  # print(w_list)

# print(h_list)
# print(w_list)

h_max_indexs = [i for i, v in enumerate(h_list) if v == max(h_list)]
# print(h_max_indexs)

w_max_indexs = [i for i, v in enumerate(w_list) if v == max(w_list)]
# print(w_max_indexs)


double_chance = False
# print("---")
for h_index in h_max_indexs:
  for w_index in w_max_indexs:
    chance = h_w_list[h_index][w_index] != "target"

    # print(h_index, w_index, chance)
    if chance:
      double_chance = True


if double_chance:
  result = h_list[h_index] + w_list[w_index]
else:
  result = h_list[h_index] + w_list[w_index] -1

print(result)


### FIXED CODE ###

H,W,M = map(int,input().split())
listh = [0] * H
listw = [0] * W
s = set()
for i in range(M):
    hm,wm = map(int,input().split())
    listh[hm-1] += 1
    listw[wm-1] += 1
    s.add((hm-1,wm-1))
mh = max(listh)
mw = max(listw)
maxh = [i for i,v in enumerate(listh) if v == mh]
maxw = [i for i,v in enumerate(listw) if v == mw]

import sys
for i in maxh:
    for j in maxw:
        if (i,j) not in s:
            print(mh + mw)
            sys.exit()
print(mh + mw - 1)
### BUGGY CODE ###

from fractions import gcd

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

ans = 0
for i in range(n):
    left, right = A[: i], A[i + 1: ]
    gcd_left, gcd_right = 0, 0
    for l in left:
        gcd_left = gcd(gcd_left, l)
    for r in right:
        gcd_right = gcd(gcd_right, r)

    ans = max(ans, gcd(gcd_left, gcd_right))

print(ans)

### FIXED CODE ###

from fractions import gcd

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

L, R = [0] * (n + 1), [0] * (n + 1)
for i in range(n):
    L[i + 1] = gcd(L[i], A[i])
    R[n - i - 1] = gcd(R[n - i], A[n - i - 1])
ans = 0
for i in range(n):
    ans = max(ans, gcd(L[i], R[i + 1]))

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

x,y,z,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

tmp=[]
for i in range(x):
    for j in range(y):
        tmp.append(a[i]+b[j])
tmp.sort(reverse=True)
ans=[]
for i in tmp[:3000]:
    for j in range(z):
        ans.append(i+c[j])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

x,y,z,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans=[]
for i in range(x):
    for j in range(y):
        if (i+1)*(j+1)>K:
            break
        for k in range(z):
            if (i+1)*(j+1)*(k+1)>K:
                break
            ans.append(a[i]+b[j]+c[k])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])