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

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

dp = [[0] * (K + 1) for i in range(N + 1)]
sdp = [[0] * (K + 1) for i in range(N + 1)]

dp[0][0] = 1
for j in range(len(dp[0])):
  sdp[0][j] = 1
  
for i in range(1, N + 1):
  for j in range(K + 1):
    dp[i][j] = sdp[i - 1][j]
    if j - A[i - 1] - 1 >= 0:
      dp[i][j] -= sdp[i - 1][j - A[i - 1] - 1]
    dp[i][j] %= DIV
  sdp[i][0] = dp[i][0]
  for j in range(1, K + 1):
    sdp[i][j] = sdp[i][j - 1] + dp[i][j]
    sdp[i][j] %= DIV
    
print(dp[N][K])

### FIXED CODE ###

import sys
readline = sys.stdin.readline

N,K = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

# dp[i][j] : i人目までにj個配るときの場合の数
# 数式変形で以下
# dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - Ai-1 - 1]

dp = [[0] * (K + 1) for i in range(N + 1)]
for i in range(N + 1):
  dp[i][0] = 1 # 0個配る方法は常に1通り
  
for i in range(1, N + 1):
  for j in range(1, K + 1):
    if j - A[i - 1] - 1 >= 0:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - A[i - 1] - 1]) % DIV
    else:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % DIV
      
print(dp[N][K])
### BUGGY CODE ###

N = int(input())
A = sorted(map(int, input().split()))
ans = 0

for i in range(0, N-2):
       for k in range(i+1, N-1):
            for l in range(k+1, N):
                if A[i]+A[k] > A[l]:
                    ans +=  1
                elif A[i]+A[k] <= A[l]:                  
                    break
print(ans)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline

N = int(input())
A = sorted(map(int, input().split()))
ans = 0
 
for i in range(0, N-2):
       for k in range(i+1, N-1):
            ans += bisect.bisect_left(A, A[i]+A[k])-k-1
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
#n=10000
#a=list(range(10**6,10**6-n,-1))
import fractions 
mod=pow(10,9)+7

b=[a,[]]
pre=0
now=1
while len(b[pre])>1:
  for i in range(0,len(b[pre])-1,2):
    b[now].append((b[pre][i]*b[pre][i+1])//fractions.gcd(b[pre][i],b[pre][i+1]))
  if len(b[pre])%2==1:
    b[now].append(b[pre][-1])
  b[pre]=[]
  now,pre=pre,now

lcma=b[pre][0]
ans=0
for ai in a:
  ans+=((lcma//ai))%mod
  ans%=mod
print(ans)


### FIXED CODE ###

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

#n=10000
#a=list(range(10**6,10**6-n,-1))

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
lcma={}
for ai in a:
  f=factorization(ai)
  for fi in f:
    if fi[0] in lcma:
      lcma[fi[0]]=max(lcma[fi[0]],fi[1])
    else:
      lcma[fi[0]]=fi[1]
l=1
for k,v in lcma.items():
  l*=pow(k,v,mod)
  l%=mod
ans=0
for ai in a:
  ans+=l*pow(ai,mod-2,mod)
  ans%=mod
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
C = list(map(int, input().split()))
query = []

for i in range(Q):
  l, r = map(int, input().split())
  query.append((i, l, r))

query.sort(key = lambda x: x[2])

class BIT:
  from operator import add, sub, mul, floordiv
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res
  
  #区間[L, R)
  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))


GJ = [-1]*N
bit = BIT([0]*N)
ans = [0]*Q
st = 0

for i in range(N):
  if GJ[C[i]-1] != -1:
    bit.set_val(GJ[C[i]-1], -1)
  GJ[C[i]-1] = i
  bit.set_val(i, 1)
  if st < Q:
    while query[st][2] == i+1:
      ans[query[st][0]] = bit.fold(query[st][1]-1, query[st][2])
      st += 1
      if st == Q:
        break

for i in ans:
  print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
C = list(map(int, input().split()))
query = []

for i in range(Q):
  l, r = map(int, input().split())
  query.append((i, l, r))

query.sort(key = lambda x: x[2])

class BIT:
  from operator import add, sub
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res

  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))

GJ = [-1]*N
bit = BIT([0]*N)
ans = [0]*Q
st = 0

for i in range(N):
  if GJ[C[i]-1] != -1:
    bit.set_val(GJ[C[i]-1], -1)
  GJ[C[i]-1] = i
  bit.set_val(i, 1)
  if st < Q:
    while query[st][2] == i+1:
      ans[query[st][0]] = bit.fold(query[st][1]-1, query[st][2])
      st += 1
      if st == Q:
        break

print(*ans, sep="\n")
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
cost = [0] * n
for i in range(1, n):
    cost[i] = min([cost[j]+abs(h[i]-h[j]) for j in range(max(0, i-k), i)])
print(cost[n-1])


### FIXED CODE ###

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

n, q = list(map(int, input().split()))
s = input().replace('AC', '+-')
for i in range(q):
  l, r = list(map(int, input().split()))
  cnt = 0
  for j in range(r - l):
    if(j + l) > r: break
    if(s[j + l - 1] == '+') and (s[j + l] == '-') : cnt += 1
  print(cnt)

### FIXED CODE ###

n, q = list(map(int, input().split()))
s = input()
cnt = 0
word_list = []
for i in range(n):
  if i > 0:
    if(s[i - 1] == 'A') and (s[i] == 'C') : cnt += 1 
  word_list.append(cnt)
for i in range(q):
  l, r = list(map(int, input().split()))
  print(word_list[r - 1] - word_list[l - 1])
### BUGGY CODE ###

tmp = input().rstrip().split()
N = int(tmp[0])
C = int(tmp[1])
dict = {}

min = 100000
max = 0

for  i in range(N):
    work = input().rstrip().split()
    if min > int(work[0]):
        min = int(work[0])
    if max < int(work[1]):
        max = int(work[1])
    if str(work[2]) in dict:
        dict[str(work[2])].append([int(work[0])-0.5,int(work[1])])
    else:
        dict[str(work[2])] = [[int(work[0])-0.5,int(work[1])]]

def myrange(x,work):
    for loop in range(len(work)):
        if work[loop][0] <= x and work[loop][1] >= x:
            return True
    return False

result = 0

for time in range(min,max+1):
    count = 0
    for k in range(C+1):
        if str(k) in dict:
            if myrange(time,dict[str(k)]):
                count +=1
    if count > result:
        result = count
print(result)

### FIXED CODE ###

N,C = map(int,input().split())
tvs = [list(map(int,input().split())) for _ in range(N)]
chans = [[] for _ in range(C+1)]
tvs.sort(key=lambda x:x[0])
targets = []
times = [0]*(pow(10,5)+2)

for tv in tvs:
  chans[tv[2]].append([tv[0],tv[1]])

for chan in chans:
  tmp = []
  if len(chan) == 1:
    targets.append(chan[0])
    continue
  for x in range(len(chan)):
    if len(tmp) == 0:
      tmp = chan[x]
      continue
    if chan[x][0] <= tmp[1] + 1:
      tmp[1] = chan[x][1]
      if x == len(chan)-1:
        targets.append(tmp)
    else:
      targets.append(tmp)
      tmp = chan[x]

for target in targets:
  times[target[0]] += 1
  times[target[1]+1] += -1

for j in range(1,pow(10,5)+2):
  times[j] += times[j-1]

print(max(times))
### BUGGY CODE ###

#142
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(1,n+1):
    b.append(a.index(i)+1)
for j in range(n):
    print(str(b[j])+' ', end="")

### FIXED CODE ###

#142改
n = int(input())
a = list(map(int, input().split()))
b = [0]*n

for i in range(n):
    b[a[i]-1] += i+1
    
for i in range(n):
    print(str(b[i])+' ', end="")
### BUGGY CODE ###

M = 1000000007

from fractions import Fraction
from bisect import bisect_left

N = int(input())

ab_zero_count = 0
a_zero_count = 0
b_zero_count = 0

fish_list = []
for _ in range(N):
	a, b = map(int, input().split())
	if a == 0 and b == 0:
		ab_zero_count += 1
	elif a == 0:
		a_zero_count += 1
	elif b == 0:
		b_zero_count += 1
	else:
		fish_list.append(Fraction(a, b))

#print(fish_list)

fish_table = {}
for f in fish_list:
	if f in fish_table:
		fish_table[f] += 1
	else:
		fish_table[f] = 1

fish_count_list = list(fish_table.items())
fish_count_list.sort()
fish_count_only_list = [f for f, c in fish_count_list]

#print(fish_count_list)

singles = 0
pair_list = []
checked = [False] * N

for i, (f, c) in enumerate(fish_count_list):
	x = -1 / f
	j = bisect_left(fish_count_only_list, x)
	if j != len(fish_count_only_list) and fish_count_only_list[j] == x:
		if checked[j] == False:
			f2, c2 = fish_count_list[j]
			pair_list.append((c, c2))
			checked[i] = True
	else:
		singles += c

if a_zero_count > 0 and b_zero_count > 0:
	pair_list.append((a_zero_count, b_zero_count))
else:
	singles += a_zero_count + b_zero_count

count = pow(2, singles, M)

#print(singles, pair_list, a_zero_count, b_zero_count)

for c1, c2 in pair_list:
	count = (count * (pow(2, c1, M) + pow(2, c2, M) - 1)) % M

count += ab_zero_count
count -= 1

print(count % M)


### FIXED CODE ###

M = 1000000007

import math

N = int(input())

ab_zero_count = 0
a_zero_count = 0
b_zero_count = 0

fish_list = []
for _ in range(N):
	a, b = map(int, input().split())
	if a == 0 and b == 0:
		ab_zero_count += 1
	elif a == 0:
		a_zero_count += 1
	elif b == 0:
		b_zero_count += 1
	else:
		if a < 0:
			a = -a
			b = -b
		g = math.gcd(a, b)
		if g > 1:
			a //= g
			b //= g
		fish_list.append((a, b))

#print(fish_list)

fish_table = {}
for f in fish_list:
	if f in fish_table:
		fish_table[f] += 1
	else:
		fish_table[f] = 1

fish_count_list = list(fish_table.items())
fish_index_table = {}
for i, (f, c) in enumerate(fish_count_list):
	fish_index_table[f] = i

#print(fish_count_list)

singles = 0
pair_list = []
checked = [False] * N

for i, (f, c) in enumerate(fish_count_list):
	a, b = f
	a, b = (-b, a)
	if a < 0:
		a = -a
		b = -b
	key = (a, b)
	if key in fish_index_table:
		j = fish_index_table[key]
		if checked[j] == False:
			f2, c2 = fish_count_list[j]
			pair_list.append((c, c2))
			checked[i] = True
	else:
		singles += c

if a_zero_count > 0 and b_zero_count > 0:
	pair_list.append((a_zero_count, b_zero_count))
else:
	singles += a_zero_count + b_zero_count

count = pow(2, singles, M)

#print(singles, pair_list, a_zero_count, b_zero_count)

for c1, c2 in pair_list:
	count = (count * (pow(2, c1, M) + pow(2, c2, M) - 1)) % M

count += ab_zero_count
count -= 1

print(count % M)
### BUGGY CODE ###

import itertools,heapq
INFTY = 10**8
N,M,R = map(int,input().split())
R = list(map(int,input().split()))
G = {}
for _ in range(M):
    A,B,C = map(int,input().split())
    if A not in G:
        G[A] = []
    G[A].append((B,C))
    if B not in G:
        G[B] = []
    G[B].append((A,C))
D = [[INFTY for j in range(N+1)] for i in range(N+1)]
for i in range(1,N+1):
    hist = [0 for _ in range(N+1)]
    heap = [(0,i)]
    while heap:
        cur = heapq.heappop(heap)
        hist[cur[1]] = 1
        for x in G[cur[1]]:
            if hist[x[0]]==0:
                if D[i][x[0]]>cur[0]+x[1]:
                    D[i][x[0]] = cur[0]+x[1]
                    heapq.heappush(heap,(D[i][x[0]],x[0]))
dmin = INFTY
for r in itertools.permutations(R,len(R)):
    d = 0
    for i in range(1,len(r)):
        d += D[r[i]][r[i-1]]
    dmin = min(dmin,d)
print(dmin)

### FIXED CODE ###

from itertools import permutations
INFTY = 10**8
N,M,R = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
d = {i:[INFTY for _ in range(N+1)] for i in range(N+1)}
for i in G:
    d[i][i] = 0
    for x in G[i]:
        d[i][x[0]] = x[1] 
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
dmin = INFTY
for x in permutations(range(R),R):
    cnt = 0
    for i in range(R-1):
        cnt += d[A[x[i]]][A[x[i+1]]]
    dmin = min(dmin,cnt)
print(dmin)
### BUGGY CODE ###

number = int(input())
lower = list(map(int, input().split()))

time = 0
max = 0

def down(i):
    global time
    for j in range(i, number-1):
        if lower[j] >= lower[j+1]:
            time += 1
        else:
            return


for i in range(len(lower)):

    if max > (number-i+1):
        break

    down(i)

    if max < time:
        max = time
    time = 0

print(max)


### FIXED CODE ###

number = int(input())
lower = list(map(int, input().split()))

time = 0
max = 0

def down(i):
    global time
    for j in range(i, number-1):
        if lower[j] >= lower[j+1]:
            time += 1
        else:
            return j+1

    return 0

now = 0
for i in range(len(lower)):

    if now > i:
        continue

    if max > (number-i+1):
        break

    now = down(i)

    if max < time:
        max = time
    time = 0



print(max)
### BUGGY CODE ###

from bisect import bisect_left
N=int(input())
ll=list(map(int,input().split()))
ll.sort()
ans=0
for i in range(N):
    for j in range(i+1,N):
        delta=bisect_left(ll,ll[i]+ll[j],lo=j)-j-1
        if delta>0:
            ans+=delta
        #print(i,j,delta)
print(ans)



### FIXED CODE ###

from bisect import bisect_left
N=int(input())
ll=list(map(int,input().split()))
ll.sort()
ans=0
for i in range(N):
    for j in range(i+1,N):
        if j==i+1:
            delta=bisect_left(ll,ll[i]+ll[i+1],lo=i+1)-i-2
            if delta>0:
                ans+=delta
            in_b=delta+i+1+1
        else:
            if in_b!=N:
                delta=bisect_left(ll,ll[i]+ll[j],lo=in_b)-j-1
            else:
                delta=N-j-1
            if delta>0:
                ans+=delta
            in_b=delta+j+1
print(ans)
### BUGGY CODE ###

n = int(input())
s_list, s_set = [], []
max_count, max_string = 0, []
for _ in range(n):
    s_list.append(input())
s_set = list(set(s_list))
for s in s_set:
    s_count = s_list.count(s)
    if s_count == max_count:
        max_string.append(s)
    elif s_count > max_count:
        max_count = s_count
        max_string.clear()
        max_string.append(s)

max_string = sorted(list(max_string))

for s in max_string:
    print(s)

### FIXED CODE ###

import collections

n = int(input())
s_list = []
for _ in range(n):
    s_list.append(input())
s_data = list(collections.Counter(s_list).most_common())
s_count = int(s_data[0][1])
s_index = 0
for s in s_data:
    if int(s[1]) == s_count:
        s_index += 1
    else:
        break
output = []
for i in range(s_index):
    output.append(s_data[i][0])
output.sort()
for s in output:
    print(s)
### BUGGY CODE ###

H,W = list(map(int, input().split()))
S = [[1 if s=='.' else 0 for s in input()] for _ in range(H)] #S[h][w]

import numpy as np
S = np.array(S)
#print(S)

SH = np.zeros((H,W), dtype='int')
SH_ = np.zeros((H,W), dtype='int')

SV = np.zeros((H,W), dtype='int')
SV_ = np.zeros((H,W), dtype='int')

#horizontal
for h in range(H):
  SH[h][0] = S[h][0]
  for w in range(1,W):
    if S[h][w]:
      SH[h][w] = SH[h][w-1] + 1
  
  SH_[h][-1] = S[h][-1]
  for w in range(W-1)[::-1]:
    if S[h][w]:
      SH_[h][w] = SH_[h][w+1] + 1
  

#vertical
for w in range(W):
  SV[0][w] = S[0][w]
  for h in range(1,H):
    if S[h][w]:
      SV[h][w] = SV[h-1][w] + 1
  
  SV_[-1][w] = S[-1][w]
  for h in range(H-1)[::-1]:
    if S[h][w]:
      SV_[h][w] = SV_[h+1][w] + 1

#print(SH + SH_)
#print(SV + SV_)

print(np.max(SH+SH_+SV+SV_) -3)

### FIXED CODE ###

H,W = list(map(int, input().split()))
S = [[0 if s=='#' else 1 for s in input()] for _ in range(H)] #S[h][w]

SH = [[0]*W for _ in range(H)]
SH_ = [[0]*W for _ in range(H)]

SV = [[0]*W for _ in range(H)]
SV_ = [[0]*W for _ in range(H)]

#horizontal
for h in range(H):
  SH[h][0] = S[h][0]
  for w in range(1,W):
    if S[h][w]:
      SH[h][w] = SH[h][w-1] + 1
  
  SH_[h][-1] = S[h][-1]
  for w in range(W-1)[::-1]:
    if S[h][w]:
      SH_[h][w] = SH_[h][w+1] + 1
  

#vertical
for w in range(W):
  SV[0][w] = S[0][w]
  for h in range(1,H):
    if S[h][w]:
      SV[h][w] = SV[h-1][w] + 1
  
  SV_[-1][w] = S[-1][w]
  for h in range(H-1)[::-1]:
    if S[h][w]:
      SV_[h][w] = SV_[h+1][w] + 1

#print(SH + SH_)
#print(SV + SV_)

ans = 0
for h in range(H):
  for w in range(W):
    ans = max(ans, SH[h][w] + SH_[h][w] + SV[h][w] + SV_[h][w] -3)

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

import math

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

result = 10**10

def vertical_and_horizontal_cal(h, w):
    global result
    area_1, area_2, area_3 = 0, 0, 0
    # - | このパターンを検証中
    for i in range(1, math.ceil(h / 2) + 1):
        area_1 = i * w
        area_2 = (h-i) * (w//2)
        area_3 = (h-i) * (w - w//2)
        diff = max(area_1, area_2, area_3) - min(area_1, area_2, area_3)
        if result > diff:
            result = diff

def vertical_and_vertical_cal(h, w):
    global result
    area_1, area_2, area_3 = 0, 0, 0
    # - - このパターンを検証中
    for i in range(1, math.ceil(h / 2) + 1):
        area_1 = i * w
        for j in range(1, math.ceil(h / 2) + 1 - i):
            area_2 = j * w
            area_3 = (h - i - j) * w
            diff = max(area_1, area_2, area_3) - min(area_1, area_2, area_3)
            if result > diff:
                result = diff

vertical_and_horizontal_cal(H, W)
vertical_and_horizontal_cal(W, H)
vertical_and_vertical_cal(H, W)
vertical_and_vertical_cal(W, H)

print(result)

### FIXED CODE ###

import math
import numpy as np

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

result = 10**10

def vertical_and_horizontal_cal(h, w):
    global result
    # - | このパターンを検証中
    for i in range(1, math.ceil(h / 2) + 1):
        area = np.array([i * w, (h-i) * (w//2), (h-i) * (w - w//2)])
        result = min(result, max(area) - min(area))

def vertical_and_vertical_cal(h, w):
    global result
    # - - このパターンを検証中
    for i in range(1, math.ceil(h / 2) + 1):
            area = np.array([i * w,  ((h-i)//2) * w, (h - i - (h-i)//2) * w])
            result = min(result, max(area) - min(area))

vertical_and_horizontal_cal(H, W)
vertical_and_horizontal_cal(W, H)
vertical_and_vertical_cal(H, W)
vertical_and_vertical_cal(W, H)

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

X = int(input())

i = 0
while True:
  tmp = X - i**5
  tmp5 = tmp**0.2
  
  if abs(tmp5 - int(tmp5)) < 1e-8:
    print("{} {}".format(i, int(tmp5)))
   
  if abs(tmp5 - int(-tmp5)) < 1e-8:
    print("{} {}".format(i, int(-tmp5)))


### FIXED CODE ###

def main():
    X = int(input())

    a = -1
    
    while True:
        b1 = 0
        b2 = 0
        while b1 < a:
            
            if (X/(a-b1)).is_integer():
                if int(X/(a-b1)) == a**4 + b1*(a**3) + (a**2)*(b1**2) + a*(b1**3) + b1**4:
                    print("{} {}\n".format(a, b1))
                    return 0

            if (X/(a-b2)).is_integer():
                if int(X/(a-b2)) == a**4 + b2*(a**3) + (a**2)*(b2**2) + a*(b2**3) + b2**4:
                    print("{} {}\n".format(a, b2))
                    return 0

            b1 += 1
            b2 -= 1
            
        a += 1


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

import sys
readline = sys.stdin.readline

n, k = map(int, readline().split())
P = 10**9 + 7

def mod_prod(a,b):
    return a * b % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n // 2
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret


if k >= n - 1:
    ans = mod_comb(n + n - 1, n - 1)
    print(ans)
else:
    ans = 0
    for i in range(k + 1):
        ans += mod_comb(n, i) * mod_comb(n - 1, i)
        ans %= P
    print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

n, k = map(int, readline().split())
P = 10**9 + 7

def mod_prod(a,b):
    return a * b % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n // 2
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret


if k >= n - 1:
    ans = mod_comb(n + n - 1, n - 1)
    print(ans)
else:
    ans = 0

    a = mod_comb(n, 0)
    b = mod_comb(n - 1, 0)
    ans = a * b % P
    for i in range(1, k + 1):
        a = mod_prod(a, (n - i + 1)) 
        a = mod_div(a, i)
        b = mod_prod(b, (n - 1 - i + 1))
        b = mod_div(b, i)
        ans += a * b % P
        ans %= P
    print(ans)
### BUGGY CODE ###

def f():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[int(j) for j in input().split()]
    import numpy as np
    #dp=np.zeros((n,n,2),dtype=np.int64)
    dp=[[[0,0]for j in range(n)] for i in range(n)]

    for i in range(1,1+n):
        for j in range(n-i+1):
            #j~j+i-1
            if i==1:
                dp[j][j][1]=a[j]
                continue
            tmp=10**18
            for k in range(i-1):
                #j~j+k,j+k+1~j+i-1
                if sum(dp[j][j+k])+sum(dp[j+k+1][j+i-1])<tmp:
                    tmp=sum(dp[j][j+k])+sum(dp[j+k+1][j+i-1])
                    dp[j][j+i-1][0]=tmp
                    dp[j][j+i-1][1]=dp[j][j+k][1]+dp[j+k+1][j+i-1][1]
    print(dp[0][n-1][0])

f()

### FIXED CODE ###

def f():
    import sys
    import numpy as np
    input=sys.stdin.readline
    n=int(input())
    a=np.array([0]+[int(j) for j in input().split()])
    np.cumsum(a,out=a)
    dp=np.zeros((n,n+1),np.int64)

    for i in range(1,n):
        l=np.arange(n-i)
        r=np.arange(i+1,n+1)
        m=(np.arange(1,i+1)+l[:,np.newaxis]).T
        dp[l,r]=np.amin(dp[l,m]+dp[m,r],0)+a[r]-a[l]
    print(dp[0][n])
f()
### BUGGY CODE ###

def sign(x):
    return (x > 0) - (x < 0)

a, b = map(int, input().split())
lst = [sign(i) for i in range(a, b + 1)]

num = 1
for l in lst:
    num *= int(l)

ans = ""
if num > 0:
    ans = "Positive"
elif num < 0:
    ans = "Negative"
else:
    ans = "Zero"
print(ans)

### FIXED CODE ###

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

ans = ""
if a < 0 and b > 0:
    ans = "Zero"
elif a > 0:
    ans = "Positive"
else:
    ans = "Positive" if abs(a - b + 1) % 2 == 0 else "Negative"

print(ans)