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

import functools
import operator
M = 10**9 + 7
n, k = map(int, input().split())
if k == 1:
    print(0)
    __import__('sys').exit(0)
a = list(map(int, input().split()))
a.sort(reverse=True)

def mul(a, b):
    ans = a * b
    if ans >= M:
        ans %= M
    return ans

def powmod(a, n):
    if n == 0:
        return 1
    if n % 2:
        ans = a * powmod(a, n - 1)
    else:
        ans = powmod(a, n // 2) ** 2
    if ans >= M:
        ans %= M
    return ans

deno = functools.reduce(mul, range(n, n - (k - 1), -1))
nume = functools.reduce(mul, range(1, k))

# max_sum = 0
# min_sum = 0
result = 0
for i, left in enumerate(range(n, k - 1, -1)):
    # print(deno // left * (left - (k - 1)))
    deno = deno * powmod(left, M - 2) * (left - (k - 1)) % M
    # print(deno // nume)
    c = deno * powmod(nume, M - 2) % M

    result += (c * a[i] % M) - (c * a[-(i + 1)] % M)
    # max_sum += c * a[i]
    # min_sum += c * a[-(i + 1)]


# print((max_sum - min_sum) % M)
print(result % M)


### FIXED CODE ###

import functools
import operator
M = 10**9 + 7
n, k = map(int, input().split())
if k == 1:
    print(0)
    __import__('sys').exit(0)
a = list(map(int, input().split()))
a.sort(reverse=True)

def mul(a, b):
    return mod(a * b)

def powmod(a, n):
    if n == 0:
        return 1
    if n % 2:
        ans = a * powmod(a, n - 1)
    else:
        ans = powmod(a, n // 2) ** 2
    return mod(ans)

def mod(a):
    if a >= M:
        a %= M
    return a
deno = functools.reduce(mul, range(n, n - (k - 1), -1))
nume = functools.reduce(mul, range(1, k))

# max_sum = 0
# min_sum = 0
result = 0
for i, left in enumerate(range(n, k - 1, -1)):
    # print(deno // left * (left - (k - 1)))
    deno = mod(mod(deno * powmod(left, M - 2)) * (left - (k - 1)))
    # print(deno // nume)
    c = mod(deno * powmod(nume, M - 2))

    result += mod(c * a[i]) - mod(c * a[-(i + 1)])
    # max_sum += c * a[i]
    # min_sum += c * a[-(i + 1)]


# print((max_sum - min_sum) % M)
print(result % M)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 09:02:00 2019
DPF
@author: maezawa
"""

s = input()
t = input()

ns = len(s)
nt = len(t)

dp = [['' for _ in range(nt+1)] for _ in range(ns+1)]

for si in range(ns):
    for ti in range(nt):
        if s[si] == t[ti]:
            arr = [dp[si][ti]+s[si], dp[si+1][ti], dp[si][ti+1]]
        else:
            arr = [dp[si+1][ti], dp[si][ti+1]]
        dp[si+1][ti+1] = max(arr, key=lambda x: len(x))
        
print(dp[ns][nt])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 09:02:00 2019
DPF3
@author: maezawa
"""

s = input()
t = input()

ns = len(s)
nt = len(t)

dp = [[0 for _ in range(nt+1)] for _ in range(ns+1)]

for si in range(ns):
    for ti in range(nt):
        if s[si] == t[ti]:
            dp[si+1][ti+1] = max(dp[si][ti]+1, dp[si+1][ti], dp[si][ti+1])
        else:
            dp[si+1][ti+1] = max(dp[si+1][ti], dp[si][ti+1])

ans = ''
si = ns
ti = nt
while si > 0 and ti > 0:
    if dp[si][ti] == dp[si-1][ti]: 
        si -= 1
    elif dp[si][ti] == dp[si][ti-1]:
        ti -= 1
    else:
        ans = s[si-1] + ans
        si -= 1
        ti -= 1

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

n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
for i, (x, h) in enumerate(xh):
    if h <= 0:
        continue
    num = h // a
    if h % a != 0:
        num += 1
    xh[i][1] -= num * a
    lis = []
    for j in range(i + 1, len(xh)):
        if xh[j][1] > 0 and xh[j][0] <= x + 2 * d:
            xh[j][1] -= num * a
    cnt += num
print(int(cnt))

### FIXED CODE ###

from math import ceil
from bisect import bisect_right
n, d, a = (int(x) for x in input().split())
xh = []
for _ in range(n):
    x, h = (int(x) for x in input().split())
    xh.append([x, h])
xh = sorted(xh, key=lambda x: x[0])
cnt = 0
dmg = [0] * (n + 1)
for i, (x, h) in enumerate(xh):
    dmg[i] += dmg[i - 1]
    h -= dmg[i]
    if h <= 0:
        continue
    num = ceil(h / a)
    dmg[i] += num * a
    idx = bisect_right(xh, [x + 2 * d, float('inf')])
    dmg[idx] -= num * a
    cnt += num
print(cnt)
### BUGGY CODE ###

import itertools

N,M,Q=map(int,input().split())
List = []

for i in range(Q):
  a = list(map(int,input().split()))
  List.append(a)
  

arr = []
for i in range(2 ** Q):
    ans = [1 for i in range(N)]
    cnt = 0
    ck = 0
    
    for j in range(Q):  # このループが一番のポイント
      if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
        a = List[j][0]
        b = List[j][1]
        c = List[j][2]
        d = List[j][3]
        cnt += d
        ans[b-1] = ans[a-1] + c

    for j in range(Q):  # このループが一番のポイント
      if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
        a = List[j][0]
        b = List[j][1]
        c = List[j][2]
        d = List[j][3]
        if ans[b-1] - ans[a-1] != c:
          ck = 1
        
    for k in range(N-1):
      if ans[k] > ans[k+1]:
        ck = 1
      elif ans[k] > M:
        ck = 1
    if ans[-1] > M:
      ck = 1
      
      
    if ck == 0:
      arr.append(cnt)

print(max(arr))




### FIXED CODE ###

import itertools

N,M,Q=map(int,input().split())
List = []

for i in range(Q):
  a = list(map(int,input().split()))
  List.append(a)
  
ans = 0

for team in itertools.combinations_with_replacement(range(1,M+1), N):
  cnt = 0
  for i in range(Q):
    a = List[i][0]
    b = List[i][1]
    c = List[i][2]
    d = List[i][3]
    
    if team[b-1] - team[a-1] == c:
      cnt += d
  ans = max(ans ,cnt)  
  
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    r = 0
    for i in reversed(range(N)):
        s = S[i]
        for j in reversed(range(i, N)):
            if s == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
            r = max(r, min(dp[i][j], j - i))
    print(r)

main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    r = 0
    for i in reversed(range(N)):
        s = S[i]
        for j in reversed(range(i, N)):
            if s == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
            r = max(r, min(dp[i][j], j - i))
    print(r)

main()
### BUGGY CODE ###

def solve():
    from bisect import bisect_left, bisect_right
    import sys
    input = sys.stdin.readline

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[iB] -= data[i]
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans
    def addRangeValue(iFr, iTo, A):
        addValue(iTo, A)
        if iFr > 0:
            addValue(iFr-1, -A)

    N, D, A = map(int, input().split())
    XHs = [tuple(map(int, input().split())) for _ in range(N)]

    XHs.sort()
    Xs = [X for X, H in XHs]
    Hs = [H for X, H in XHs]

    data, numPow2 = makeBIT(N)
    setInit(Hs)

    ans = 0
    for iL in range(N):
        H = getValue(iL)
        if H <= 0: continue
        iR = bisect_right(Xs, Xs[iL]+2*D) - 1
        num = -(-H // A)
        addRangeValue(iL, iR, -num*A)
        ans += num

    print(ans)


solve()


### FIXED CODE ###

def solve():
    from bisect import bisect_left, bisect_right
    import sys
    input = sys.stdin.readline

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[iB] -= data[i]
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans
    def addRangeValue(iFr, iTo, A):
        addValue(iTo, A)
        if iFr > 0:
            addValue(iFr-1, -A)

    N, D, A = map(int, input().split())
    XHs = [tuple(map(int, input().split())) for _ in range(N)]

    XHs.sort()
    Xs = [X for X, H in XHs]
    Hs = [H for X, H in XHs]

    data, numPow2 = makeBIT(N)
    setInit(Hs)

    ans = 0
    for iL in range(N):
        H = getValue(iL)
        if H <= 0: continue
        iR = bisect_right(Xs, Xs[iL]+2*D) - 1
        num = -(-H // A)
        addRangeValue(iL, iR, -num*A)
        ans += num

    print(ans)


solve()
### BUGGY CODE ###

n = int(input())

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

total = sum(a)
ans = float("inf")
for i in range(n-1):
  x = sum(a[:i+1])
  y = total - x
  if(abs(x-y) < ans):
    ans = abs(x-y)
    
print(ans)

### FIXED CODE ###

n = int(input())

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

total = sum(a)
x = 0
ans = float("inf")
for i in range(n-1):
  x += a[i]
  y = total - x
  if(abs(x-y) < ans):
    ans = abs(x-y)
    
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N=input()

#素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

ans=1
for i in range(2,N+1):
    L=factorization(i)
    fi=1
    for x,y in L:
        fi*=(y+1)
    ans+=i*fi
print ans

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
N=input()
A=[ 2 for _ in range(N+1)]
A[0]=0
A[1]=1

for cur in range(2,N+1):
    for i in range(cur*2,N+1,cur):
        A[i]+=1

ans=0
for i in range(1,N+1):
    ans+=i*A[i]
print ans
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
f = [0] * N
for i in range(1, N+1):
  count = 0
  for x in range(1, i):
    for y in range(x, i):
      z = i-x-y
      if z < y:
        break
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if n <= N:
        if x == y and x == z:
          f[n-1] += 1
        elif x == y or y == z:
          f[n-1] += 3
        elif x != y and x != z and y != z:
          f[n-1] += 6
for i in f:
  print(i)

### FIXED CODE ###

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

N = int(input())
f = [0] * N
for i in range(1, N+1):
  count = 0
  for x in range(1, i):
    if x**2 > N:
      break
    for y in range(x, i):
      if y**2 > N:
        break
      z = i-x-y
      if z < y:
        break
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if z > math.sqrt(n + 1):
        break
      if n <= N:
        if x == y and x == z:
          f[n-1] += 1
        elif x == y or y == z:
          f[n-1] += 3
        elif x != y and x != z and y != z:
          f[n-1] += 6
for i in f:
  print(i)
### BUGGY CODE ###

n = int(input())
tot=0
dp = [0 for i in range(n+4)]
for i in range(1, n+1):
	tot=tot+i
	if tot>=n:
		print(i)
		break

### FIXED CODE ###

n = int(input())
tot=0
for i in range(1, n+1):
	tot=tot+i
	if tot>=n:
		print(i)
		break
### BUGGY CODE ###

mod = 10 ** 9 + 7
N = 2 * 10 ** 6

fac = [0] * N
finv = [0] * N
inv = [0] * N

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, N):
    fac[i] = fac[i - 1] * i % mod
    # mod pにおける1, 2, ..., nの逆元
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def com(n, k):
    global fac, finv, mod
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


r1, c1, r2, c2 = map(int, input().split())
answer = 0

for r in range(r1, r2 + 1):
    for c in range(c1, c2 + 1):
        answer += com(r + c, c)
        answer %= mod
print(answer)


### FIXED CODE ###

mod = 10 ** 9 + 7
N = 2 * 10 ** 6 + 10

fac = [0] * N
finv = [0] * N
inv = [0] * N

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, N):
    fac[i] = fac[i - 1] * i % mod
    # mod pにおける1, 2, ..., nの逆元
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def com(n, k):
    global fac, finv, mod
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod

def g(r, c):
    return (com(r + c + 2, r + 1) - 1) % mod

r1, c1, r2, c2 = map(int, input().split())

answer = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
answer %= mod
print(answer)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=list(input())
count_list=[]

flag=0
for i in range((N+1)//2):
    if S[i*2]=='A':
        if i*2!=len(S)-1:
            if S[(i*2)+1]=='C': count_list.append(i*2+1)
    elif S[i*2]=='C':
        if i*2!=0:
            if S[(i*2)-1]=='A': count_list.append(i*2)

for i in range(Q):
    l,r=map(int,input().split())
    l,r=l-1,r-1 #リストのインデックスとの整合
    n=sum(l+1<=x<= r for x in count_list)
    print(max(n,0))

### FIXED CODE ###

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

import math
N,M = [int(X) for X  in input().split()]
A = [int(X) for X  in input().split()]
for i in range(M):
  A[A.index(max(A))] /=2

ans = 0
for i in A:
  ans += math.floor(i)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, m = MI()
    a = LI()
    heap = []
    for i in range(n):
        heapq.heappush(heap, a[i] * -1)

    while m > 0:
        min_ = heapq.heappop(heap) * -1
        min_ = (min_ // 2) * -1
        heapq.heappush(heap, min_)
        m -= 1
    print(sum(heap) * -1)


main()
### BUGGY CODE ###

n,m = map(int,input().split())
lr = [[] for i in range(m)]
cnt = 0
for _ in range(m):
    l,r = map(int,input().split())
    lr[_].append(l)
    lr[_].append(r)

for nn in range(1,n+1):
    ok = True
    for ran in lr:
        if ran[0] > nn or ran[1] < nn:
            ok = False
    if ok:
        cnt += 1
print(cnt)

### FIXED CODE ###

n,m = map(int,input().split())
ls = [i for i in range(m)]
rs = [i for i in range(m)]
cnt = 0
for _ in range(m):
    ls[_],rs[_] = map(int,input().split())

maxl = max(ls)
minr = min(rs)

for nn in range(1,n+1):
    if maxl <= nn and minr >= nn:
        cnt += 1
print(cnt)
### BUGGY CODE ###

from math import gcd

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

L = N*M // gcd(N, M)
for i in range(N):
    for j in range(M):
        if M*i == N*j and S[i] != T[j]:
            print(-1)
            exit()

print(L)


### FIXED CODE ###

from math import gcd

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

L = N*M // gcd(N, M)

for i in range(N):
    if M*i % N == 0:
        j = M*i // N
        if S[i] != T[j]:
            print(-1)
            exit()

print(L)
### BUGGY CODE ###

def judge(a,b,c,d):
    #calc border
    if a-c<0:
        border = 0
    else:
        if (a-c)%b == 0:
            border = int((a-c)/b)
        else:           
            border = int((a-c)/b)+1

    start = a-border*b

    return start
    
def check(a,b,c,d):
    if a-b<0:
        return False
    if d<b:
        return False
    if c>=b and d>=b:
        return True
#    if b%2==0 and d%2==0:
#        if (c-b+2)<0:
#            return False
#    elif (c-b+1)<0:
#        return False
    
    ans = judge(a,b,c,d)
    b_list = []
    while not ans in b_list:
        b_list.append(ans)
        if ans <= c:
            a = ans+d
        else:
            a = ans
        if a-b<0:
            return False

        ans = judge(a,b,c,d)
        if ans < 0:
            return False
    
    return True
  
N = int(input())
ABCD = []
for i in range(N):
    ABCD.append(map(int, input().split()))


for a,b,c,d in ABCD:
    if check(a,b,c,d):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###


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


def judge(a,b,c,d):
    if a<b or d<b:
        return False
    elif c >= b:
        return True
    else:
        g = findGCD(b,d)
        thr = b-g+a%g
        if thr > c:
            return False
        else:
            return True
        
T = int(input())
ABCD = []
for i in range(T):
    ABCD.append(list(map(int, input().split())))
        
for a,b,c,d in ABCD:
    if judge(a,b,c,d):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n, x, y = map(int, input().split())
lis = []
for i in range(1, n):
    for j in range(i+1, n+1):
        lis.append(min([j-i, abs(x-i)+1+abs(y-j), abs(y-i)+1+abs(x-j)]))
for i in range(1, n):
    print(lis.count(i))

### FIXED CODE ###

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

n,k=map(int,input().split())
l=list(map(int,input().split()))
el=[]
for i in l[:]:
    el.append((1+i)/2)
ans=0
for i in range(n-k+1):
    ans = sum(el[i:i+k]) if sum(el[i:i+k]) > ans else ans
print(ans)

### FIXED CODE ###

import queue
n,k=map(int,input().split())
l=list(map(int,input().split()))
el=queue.deque(maxlen=k)
ans = 0
m = 0
for i in l[:]:
    if len(el) == k:
        el.append((1+i)/2)
        m = m-m_e+el[-1]
    else:
        el.append((1+i)/2)
        m +=el[-1]
    ans = m if m>ans else ans
    m_e = el[0]
print(ans)
### BUGGY CODE ###

A, B = map(int, input().split())
ans = 0
cnt = 0
def f(arg):
    ans = 0
    for pos in range(40):
        v = 1 << pos
        if v > arg:
            break
        cnt = sum([int((n & v) / v) for n in range(arg+1)])
        ans += cnt%2 * v
    return ans
print(f(A-1)^f(B))


### FIXED CODE ###

A, B = map(int, input().split())
ans = 0
cnt = 0
def f(arg):
    ans = 0
    if arg < 0:
        return 0
    for pos in range(1, 41):
        # ループする数
        loop = 1 << pos
        # cnt = sum([int((n & v) / v) for n in range(arg+1)])
        cnt = int((arg + 1) / loop) * (loop >> 1)
        cnt += max(0, (arg + 1) % (loop) - (loop >> 1))
        ans += cnt%2 * (loop>>1)
        # print(arg, pos, loop, cnt, ans)
        if loop > arg:
            break
    return ans
print(f(A-1)^f(B))
### BUGGY CODE ###

import sys
import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N = I()
	a = np.zeros((N,))
	b = np.zeros((N,))
	c = np.zeros((N,))
	for i in range(N):
		a[i], b[i], c[i] = LI()
	
	dp = np.zeros((N, 3), dtype=int)
	for i in range(N):
		if i == 0:
			dp[i, 0] = a[i]
			dp[i, 1] = b[i]
			dp[i, 2] = c[i]
		else:
			dp[i, 0] = max(dp[i-1, 1] + a[i], dp[i-1, 2] + a[i])
			dp[i, 1] = max(dp[i-1, 0] + b[i], dp[i-1, 2] + b[i])
			dp[i, 2] = max(dp[i-1, 0] + c[i], dp[i-1, 1] + c[i])
	print(np.max(dp[-1, :]))

if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
# import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N = I()
	activity = []
	for i in range(N):
		activity.append(LI())
	
	# dp = np.zeros((N, 3), dtype=int)
	dp = [[0, 0, 0] for _ in range(N)]
	dp[0][0] = activity[0][0]
	dp[0][1] = activity[0][1]
	dp[0][2] = activity[0][2]
	for i in range(1, N):
		dp[i][0] = max(dp[i-1][1] + activity[i][0], dp[i-1][2] + activity[i][0])
		dp[i][1] = max(dp[i-1][0] + activity[i][1], dp[i-1][2] + activity[i][1])
		dp[i][2] = max(dp[i-1][0] + activity[i][2], dp[i-1][1] + activity[i][2])
	print(max(dp[-1]))

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

r, g, b, n = map(int, input().split())

count = 0
r, g, b = sorted([r, g, b])


for i in range(n // r + 1):
    total = r * i
    if total > n:
        continue
    for j in range((n - total) // g + 1):
        total = r * i + g * j
        if total > n:
            continue
        for k in range((n - total) // b + 1):
            total = r * i + g * j + b * k
            if total == n:
                count += 1

print(count)


### FIXED CODE ###

r, g, b, n = map(int, input().split())

count = 0
r, g, b = sorted([r, g, b], reverse=True)


for i in range(n // r + 1):
    rc = r * i
    for j in range((n - rc) // g + 1):
        gc = g * j
        if (n - rc - gc) % b == 0:
            count += 1
print(count)
### BUGGY CODE ###

import bisect

N = int(input())

tops = []

for i in range(N):
    a = int(input())
    # 二分探索
    p = bisect.bisect_left(tops, a)
    
    if p == 0:
        bisect.insort_left(tops, a)
    else:    
        tops[p-1] = a
        
print(len(tops))


### FIXED CODE ###

import bisect
from collections import deque

N = int(input())

tops = deque() 

for i in range(N):
    a = int(input())
    p = bisect.bisect_left(tops, a)
    
    if p == 0:
        tops.appendleft(a)
    else:    
        tops[p-1] = a
        
print(len(tops))
### BUGGY CODE ###

import scipy.misc as scm
mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

num = [-1] * (n+1)
l = r = -1
for i in range(len(a)):
    if num[a[i]] != -1:
        l, r = num[a[i]], i
        break
    num[a[i]] = i

for k in range(1, len(a)+1):
   print(scm.comb(len(a), k, True) % mod - scm.comb(l+len(a)-r-1, k-1, True) % mod)

### FIXED CODE ###

# ------ combination -------
N, MOD = 10**5 + 1, 10**9 + 7
fc, ifc = [0] * (N+1), [0] * (N+1)

def power(n, a):
    res, exp = 1, n
    while(a):
        if a & 1:
            res = res * exp % MOD
        exp = exp * exp % MOD
        a = a >> 1
    return res

fc[0] = 1
for i in range(1, N+1):
    fc[i] = fc[i-1] * i % MOD
ifc[N] = power(fc[N], MOD-2)
for i in range(N-1, -1, -1):
    ifc[i] = ifc[i+1] * (i+1) % MOD

def Comb(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    return fc[n] * ifc[r] % MOD * ifc[n-r] % MOD

# --------------------------

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

num = [-1] * (n+1)
l = r = -1
for i in range(len(a)):
    if num[a[i]] != -1:
        l, r = num[a[i]], i
        break
    num[a[i]] = i

for k in range(1, len(a)+1):
    ans = Comb(len(a), k) - Comb(l+len(a)-r-1, k-1)
    while ans < 0:
        ans += MOD
    print(ans)
### BUGGY CODE ###

import heapq
import sys
sys.setrecursionlimit(10**6)
from collections import deque

H,W = map(int,input().split())
INF = 10**18
q = deque()

d = [[INF]*W for _ in range(H)] # '#'からの距離

for i in range(H):
  txt = input()
  for j,c in enumerate(txt):
    if c == '#':
      d[i][j] = 0
      q.append((0,i,j))

      
ans = 0
while q:
  dv,x,y = q.popleft()
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx][yy] == INF:
      d[xx][yy] = dv+1
      ans = dv+1
      q.append((dv+1,xx,yy))

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)