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

#!/usr/bin/env python3
import sys

#count '<'
def count_S(S, N):
    ret=S.find('>')
    #print("<",S,N,ret)
    if ret==-1:
        ret=N
    return ret

#count '>'
def count_L(S, N):
    ret=S.find('<')
    if ret==-1:
        ret=N
    #print(">",S,N,ret)
    return ret

def count_L_slow(S, N):
    ret=0
    for i in range(N):
        if S[i:i+1]=='>':
            ret+=1
        else:
            break
    return ret

def solve(S: str):
    answer=0
    
    i=0
    old_s=old_l=0
    while i<len(S):
        cnt_s=count_S(S[i:],len(S[i:]))
        cnt_l=count_L(S[i:],len(S[i:]))
        answer+=(cnt_s+1)*cnt_s//2
        if cnt_s==0:
            if cnt_l>old_s:
               answer-=old_s
            else:
               answer-=cnt_l
        answer+=(cnt_l+1)*cnt_l//2
        #print("cnt_s,cnt_l",cnt_s, cnt_l,answer)
        old_s=cnt_s
        old_l=cnt_l
        i+=cnt_s+cnt_l

    print(answer)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

#count '<'
def count_S(S, N):
    ret=S.find('>')
    #print("<",S,N,ret)
    if ret==-1:
        ret=N
    return ret

#count '>'
def count_L(S, N):
    ret=S.find('<')
    if ret==-1:
        ret=N
    #print(">",S,N,ret)
    return ret

def count_S_slow(S, ns, N):
    ret=0
    for i in range(ns,N):
        if S[i:i+1]=='<':
            ret+=1
        else:
            break
    return ret

def count_L_slow(S, ns, N):
    ret=0
    for i in range(ns,N):
        if S[i:i+1]=='>':
            ret+=1
        else:
            break
    return ret

def solve(S: str):
    answer=0
    
    numS=len(S)
    cnt_l=count_L(S,len(S))
    answer+=(cnt_l+1)*cnt_l//2
    i=cnt_l
    while i<len(S):
        cnt_s=count_S_slow(S,i,numS)
        cnt_l=count_L_slow(S,i+cnt_s,numS)
        answer+=(cnt_s+1)*cnt_s//2
        answer+=(cnt_l+1)*cnt_l//2
        if cnt_l>cnt_s:
           answer-=cnt_s
        else:
           answer-=cnt_l
        #answer+=(cnt_l+1)*cnt_l//2
        #print("cnt_s,cnt_l",cnt_s, cnt_l,answer)
        i+=cnt_s+cnt_l

    print(answer)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

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

# coding: utf-8
# Your code here!
N, M = map(int, input().split())
List = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

SumList = [sum(List)]

i=0
while i<M:
    CheckList = List
    
    j=0
    while j<BC[i][0]:
        CheckList[CheckList.index(min(CheckList))] = BC[i][1]
        j+=1
        
    SumList.append(sum(CheckList))
        
    i+=1

print(max(SumList))

### FIXED CODE ###

import numpy as np
 
N,M = map(int,input().split())
 
A = np.array([int(x) for x in input().split()],dtype=np.int64)
A.sort()
 
BC = np.array([[int(x) for x in input().split()] for _ in range(M)])
B = BC[:,0]
C = BC[:,1]
 
idx = C.argsort()
B = B[idx][::-1]
C = C[idx][::-1]
 
p = 0
for b,c in zip(B,C):
  A[p:p+b] = np.maximum(A[p:p+b],c)
  p += b
 
answer = A.sum()
print(answer)
### BUGGY CODE ###

def main():
    n, m, k = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(m)]
    CD = [[int(e) for e in input().split()] for i in range(k)]

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for ab in AB:
        Df[ab[0]].add(ab[1])
        Df[ab[1]].add(ab[0])

    for cd in CD:
        Db[cd[0]].add(cd[1])
        Db[cd[1]].add(cd[0])

    Q = []
    ANS = []
    for i in range(1, n + 1):
        FF = set()
        C = [False]*(n + 1)
        C[i] = True
        Q.append(i)
        while len(Q) != 0:
            for f in Df[Q.pop(0)]:
                if not C[f]:
                    Q.append(f)
                    FF.add(f)
                    C[f] = True

        ANS.append(C.count(True) - len(Df[i]) - len(FF & Db[i] - Df[i]) - 1)

    print(*ANS)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

def main():
    n, m, k = [int(e) for e in input().split()]

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for i in range(m):
        a, b = [int(e) for e in input().split()]
        Df.get(a).add(b)
        Df.get(b).add(a)

    for i in range(k):
        c, d = [int(e) for e in input().split()]
        Db.get(c).add(d)
        Db.get(d).add(c)

    Q = deque()
    C = set()
    ANS = {}
    for i in range(1, n + 1):
        if i in C:
            continue

        C.add(i)
        Cin = set()
        Cin.add(i)
        Q.appendleft(i)
        while len(Q) != 0:
            for f in Df.get(Q.pop()) - Cin:
                Q.appendleft(f)
                C.add(f)
                Cin.add(f)

        for k in Cin:
            ANS[k] = len(Cin) - len(Df[k]) - len(Cin & Db[k] - Df[k]) - 1

    print(*[ANS[i] for i in range(1, n + 1)])

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

K = int(input())
count = 1
n = 7
while True:
    if K % 2 == 0 or K % 5 == 0:
        count = -1
        break
    if n % K == 0:
        break
    n += 7*10**count
    count += 1
print(count)

### FIXED CODE ###

K = int(input())
count = 1
n = 0
if K % 2 == 0 or K % 5 == 0:
    count = -1
    print(count)
else:
    while True:
        n = (n*10+7)%K
        if n == 0:
            break
        count += 1
    print(count)
### BUGGY CODE ###

K=int(input())
queue=[1,2,3,4,5,6,7,8,9]
for i in range(K-1):
    t=queue.pop(0)
    if t%10!=0:
        queue.append(t*10+pow(t,1,10)-1)
    queue.append(t*10+pow(t,1,10))
    if t%10!=9:
        queue.append(t*10+pow(t,1,10)+1)
print(queue[0])

### FIXED CODE ###

K=int(input())
queue=[1,2,3,4,5,6,7,8,9]
count=0
for i in range(K-1):
    t=queue[i]
    if t%10!=0:
        queue.append(t*10+pow(t,1,10)-1)
    queue.append(t*10+pow(t,1,10))
    if t%10!=9:
        queue.append(t*10+pow(t,1,10)+1)
print(queue[K-1])
### BUGGY CODE ###

n,m = map(int,input().split())

pref_list = list()
jyunban = list()

for i in range(n):
    pref_list.append(list())
    
for i in range(m):
    p,y = map(int,input().split())
    pref_list[p-1].append(y)
    jyunban.append([p,y])
    
for pref in pref_list:
    pref.sort()

for pref,year in jyunban:
    index = pref_list[pref-1].index(year) + 1
    pref = str(pref).rjust(6,'0')
    index = str(index).rjust(6,'0')
    print(pref+index)

### FIXED CODE ###

n,m = list(map(int,input().split()))
tmp = [list(map(int,input().split())) for i in range(m)]
cities = [[] for i in range(n+1)]


for i,(pref,year) in enumerate(tmp):
    cities[pref].append([year,i])
    
answers = [""] * m
for i in range(n+1):
    for j,(year,index) in enumerate(sorted(cities[i])):
        answer = str(i).zfill(6) + str(j+1).zfill(6)
        answers[index] = answer
        
print(*answers,sep=("\n"))
### BUGGY CODE ###

import numpy as np
import math
x = int(input())
for a in range(10**10):
    fp = True
    fm = True
    f = False
    for b in range(10**10):
        if fp:
            if a**5-b**5 == x:
                print(a,b)
                f = True
                break
            elif a**5-b**5 > x:
                fp = False
        if fm:
            if a**5+b**5 == x:
                print(a,-b)
                f = True
                break
            elif a**5+b**5 > x:
                fp = False
        if not (fp and fm):
            break
    if f:
        break

### FIXED CODE ###

import numpy as np
import math
x = int(input())
ys = []
i = 1
while i**2 < x:
    if x%i == 0:
        ys.append(i)
        ys.append(x//i)
    i += 1
if i**2 == x:
    ys.append(i)

f = False

for j in ys:
    for i in range(10**3):
        if i**5-(i-j)**5 == x:
            print(i,i-j)
            break
        elif i**5-(i-j)**5 > x and i-j > 0:
            break
    if f:
        break
### BUGGY CODE ###

#!/usr/bin/env python
 
import sys
import numpy as np
 
s= sys.stdin.readline().strip()
#
MOD=10**9+7
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ (b*i)%13 for i in range(10) ] )
#
dp= np.zeros( shape=(13),dtype=np.int64 )
dp[0] = 1
for i,c in enumerate(reversed(s)):
    tmp  = dp.copy()
    #
    if c=="?":
        bset = mmap[i%6][1:]
        for m in range(13):
            num= tmp[m]
            if num==0: continue
            for b in bset:
                idx= (m+b)%13
                dp[idx]= ( dp[idx] + num ) % MOD
    else:
        b= mmap[i%6][int(c)]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
#
print(dp[5])


### FIXED CODE ###

import sys
 
s= sys.stdin.readline().strip()
#
MOD=10**9+7
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ [ (b*i+j)%13 for i in range(1,10) ] for j in range(13) ] )
#
dp= [ 0 ] * 13
dp[0] = 1
j= 0
for c in reversed(s):
    tmp = dp.copy()
    #
    if c=="0": pass
    elif c=="?":
        bset = mmap[j]
        for m,num in enumerate(tmp):
            if num==0: continue
            for idx in bset[m]: dp[idx]+=num
        #
        for i in range(13): dp[i]%=MOD
    else:
        b= mmap[j][0][int(c)-1]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
    #
    if j==5: j=0
    else: j+=1
#
print(dp[5])
### BUGGY CODE ###

import itertools
n = int(input())
ary = []
for i in range(n):
    s = input()[0]
    if s == "M" or s == "A" or s =="R" or s =="C" or s == "H":
        ary.append(s)
print(len([ i for i in itertools.combinations(ary,3) if len(set(i)) == 3]))

### FIXED CODE ###

from collections import Counter
import itertools
n = int(input())
ary = []
for i in range(n):
    s = input()[0]
    if s == "M" or s == "A" or s =="R" or s =="C" or s == "H":
        ary.append(s)
count = Counter(ary)
s = set(count.keys())
cnb = list(itertools.combinations(s,3))
ans = 0
for a,b,c in cnb:
    ans += count[a] * count[b] * count[c]
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
price = list(map(int, input().split()))
for i in range(M):
  price[price.index(max(price))] //= 2

print(sum(price))

### FIXED CODE ###

from heapq import heappop, heappush

N, M = map(int, input().split())
price = list(map(int, input().split()))
he = []
for i in price:
  heappush(he, -i)
for i in range(M):
  max = heappop(he)
  heappush(he, -(-max//2))
print(-sum(he))
### BUGGY CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

from fractions import Fraction

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        ratio = Fraction(a,b)
        before = cnd.get(ratio,False)
        if before:
            cnd[ratio] = [before[0]+1,before[1]]
        else:
            invratio = Fraction(-b,a)
            check = cnd.get(invratio,False)
            if check:
                cnd[invratio] = [check[0],check[1]+1]
            else:
                cnd[ratio] = [1,0]

cnd[0] = [azero,bzero]
noreg = 0
ans = 1
#print(cnd)
for item in cnd.values():
    if item[0] == 0  or item[1] == 0:
        noreg += max(item[0],item[1])
    else:
        ans *= (2**item[0]%mod+2**item[1]%mod-1)%mod
        ans %= mod
#print('hoge')
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))

### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

#from fractions import Fraction
from math import gcd

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        '''
        ratio = Fraction(a,b)
        before = cnd.get(ratio,False)
        if before:
            cnd[ratio] = [before[0]+1,before[1]]
        else:
            invratio = Fraction(-b,a)
            check = cnd.get(invratio,False)
            if check:
                cnd[invratio] = [check[0],check[1]+1]
            else:
                cnd[ratio] = [1,0]
        '''
        g = gcd(a,b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        cnd[(a,b)] = cnd.get((a,b),0)+1


noreg = 0
if azero == 0 or bzero == 0:
    noreg += max(azero,bzero)
    ans = 1
else:
    ans = (2**azero%mod + 2**bzero%mod - 1)%mod
#print('ans block')
#print(ans,noreg)
#print(cnd)
for k,item in cnd.items():
    a,b = k
    if b>0:
        m = cnd.get((b,-a),False)
        if m:
            ans *= (2**item%mod+2**m%mod-1)%mod
        else:
            noreg += item
    else:
        m = cnd.get((-b,a),False)
        if not m:
            noreg += item
#print('hoge')
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
A = [0 for i in range(N)]
a = 0
if S[0] == 'A':
  a = 1
for i in range(1,N):
  if a == 1 and S[i] == 'C':
    A[i] = 1
    a = 0
  if S[i] == 'A':
    a = 1
  else:
    a = 0
for i in range(Q):
  l, r = map(int, input().split())
  T = A[l:r]
  ans = sum(T)
  print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
A = []
a = 0
for i in range(N-1):
  if S[i] == 'A' and S[i+1] == 'C':
    a += 1
    A.append(a)
  else:
    A.append(a)
for i in range(Q):
  l, r = map(int, input().split())
  if l>=2:
    ans = A[r-2]-A[l-2]
    print(ans)
  else:
    ans = A[r-2]
    print(ans)
### BUGGY CODE ###

n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())

for _ in range(q):
    l,r = map(int, input().split())
    s = 0

    for j in range(l,r+1,d):
        if j!=l:
            s+= abs(buf[j][0] - buf[j-d][0]) + abs(buf[j][1] - buf[j-d][1])
    print(s)
            

### FIXED CODE ###

n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

cost = [0] * ((n*m)+1)

for i in range(d+1,n*m+1):
    cost[i] = cost[i-d] + abs(buf[i-d][0] - buf[i][0]) + abs(buf[i-d][1] - buf[i][1])

for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])
    

for l,r in al:
    print(cost[r]-cost[l])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a.reverse()
lis = [2,5,5,4,5,6,3,7,6]
mat=[]
for num in a:
    mat.append([num,lis[num-1]])

def new_val(num1,num2): # 123 , 4 -> 4123
    if num1<0:
        return -(10**10)
    if num1==0:
        return num2

    return int(str(num1)+str(num2))

dp = [[-(10**10) for i in range(1+n)] for j in range(1+m)]
for i in range(m):
    dp[i][0]=0

for i in range(m):
    num=mat[i][0]
    honsu=mat[i][1]
    for j in range(1+n):
        if j<honsu:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(new_val(dp[i+1][j-honsu] , num),dp[i][j])
print(dp[-1][-1])

### FIXED CODE ###

n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
lis = [2,5,5,4,5,6,3,7,6]
def new_val(num1,num2): # 123 , 4 -> 1234
    if num1<0:
        return -(10**10)
    if num1==0:
        return num2
    ret = (10**len(str(num2)))*num1 + num2
    return ret

dp = [[-(10**10) for i in range(1+n)] for j in range(1+m)]
for i in range(m):
    dp[i][0]=0

for i in range(m):
    num=a[i]
    honsu=lis[a[i]-1]
    for j in range(1+n):
        if j<honsu:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(new_val(dp[i+1][j-honsu] , num),dp[i][j])
print(dp[-1][-1])
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
m = []
s = []
j = 0
for i in range(1, 1001):
    j += i
    s.append(j/i) 

for i in range(n-k+1):
    l.append(p[i:i+k])
    m.append(sum(p[i:i+k]))
Max_index = m.index(max(m))

ll = l[Max_index]
ans = 0
for i in ll:
    ans += s[i-1]
print(ans) 

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
y = 0
for x in range(1, 1001):
    y += x
    l.append(y/x)
m = []
for i in p:
    m.append(l[i-1])
s = [0]
z = 0
for i in m:
    z += i
    s.append(z)
ans = 0
for i in range(n-k+1):
    ans = max(ans, s[i+k] - s[i])
print(ans)
### BUGGY CODE ###

a, b = map(int,input().split())
 
def cf(x1,x2):
  cf=[]
  for i in range(2,min(x1,x2)+1):
    if x1 % i == 0 and x2 % i == 0:
      cf.append(i)
  return cf
 
List = cf(a, b)
import fractions
 
def check(x1, x2):
  if fractions.gcd(x1, x2) == 1:
    return 1
  else:
    return 0
 
 
Answer = []
for i in range(len(List)):
  if i == 0:
    Answer.append(List[i])
  else:
    checker = 1
    for j in range(len(Answer)):
      if check(Answer[j], List[i]) == 0:
        checker = 0
        break
    if checker == 1:
      Answer.append(List[i])

print(len(Answer)+1)

### FIXED CODE ###

import fractions
A,B = map(int,input().split())
x = fractions.gcd(A,B)
pf = {}
for i in range(2,int(x**0.5)+2):
  while x%i == 0:
    pf[i] = pf.get(i,0) +1
    x //= i
if x > 1:
  pf[x] = 1
print(len(pf)+1)
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp[i][j][k] := j番目の要素まで見て、総和がjで、使う区間がk=0,1,2(0:未確定, 1:L確定済, 2:LR確定済)の状態の通り数
dp = list3d(N+1, S+1, 3, 0)
dp[0][0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        for k in range(3):
            if dp[i][j][k] == 0:
                continue
            for l in range(k, 3):
                # aを総和に足さない遷移は全部OK
                dp[i+1][j][l] += dp[i][j][k]
                # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
                if j+a <= S and k != 2 and l != 0:
                    dp[i+1][j+a][l] += dp[i][j][k]
ans = dp[N][S][2] % MOD
print(ans)


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp0[i][j][ := j番目の要素まで見て、総和がjで、使う区間が未確定の状態の通り数
dp0 = list2d(N+1, S+1, 0)
# dp1[i][j][ := j番目の要素まで見て、総和がjで、使う区間がL確定済の状態の通り数
dp1 = list2d(N+1, S+1, 0)
# dp2[i][j][ := j番目の要素まで見て、総和がjで、使う区間がLR確定済の状態の通り数
dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は全部OK
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            dp1[i+1][j+a] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+a] += dp0[i][j] + dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce

def nCr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
  
from itertools import combinations
MOD = 10**9+7

n,k = map(int,input().split())
aa = list(map(int,input().split()))

aa = sorted(aa)
  
ans = 0
for i in range(n-1,k-2,-1):
  ans += aa[i] * nCr(i,k-1)
  ans %= MOD
  
r_aa = list(reversed(aa))
for i in range(n-1,k-2,-1):
  ans -= r_aa[i] * nCr(i,k-1)
  ans %= MOD
  
print(ans)  

### FIXED CODE ###

mod = 10**9 + 7

N_MAX = 10**5+1
fact = [1] * N_MAX
for i in range(1,N_MAX):
  fact[i] = (fact[i-1]*i) % mod
  
def nCr(n,r):  
  if n < r:
    return 0
  return (fact[n] * pow(fact[r]*fact[n-r] ,mod-2,mod))% mod

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

mi = 0
ma = 0

for i in range(1,n):
  m = nCr(n-i,k-1)
  mi += A[i-1] * m
  ma += A[-i]  * m
  
print((ma - mi)%mod)
### BUGGY CODE ###

x = int(input())
for a in range(-1000000, 1000001):
    p = a ** 5
    l, r = -100000000, 100000001
    while r - l > 1:
        m = (l + r) // 2
        if m ** 5 <= p - x:
            l = m
        else:
            r = m
    if l ** 5 == p - x:
        print(p, l)
        exit(0)


### FIXED CODE ###

x = int(input())
for a in range(-10000, 10001):
    p = a ** 5
    l, r = -10000, 10001
    while r - l > 1:
        m = (l + r) // 2
        if m ** 5 <= p - x:
            l = m
        else:
            r = m
    if l ** 5 == p - x:
        print(a, l)
        exit(0)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  h,p = list(map(int, input().split()))
  A.append([h+p,h,p])
  
A.sort()

# N人積んだ時の最小の高さH
dp = [-1 for i in range(N+1)]
dp[0] = 0

for i in range(N):
  _,h,p = A[i]
  for j in range(N, 0, -1):
    ## まだj-1人積んだことがない
    if dp[j-1] < 0:
      continue
    ## 高すぎてつめない
    if dp[j-1] > h:
      continue
    if dp[j] < 0:
      dp[j] = dp[j-1] + p
    else:
      dp[j] = min(dp[j], dp[j-1] + p)
    
for i in range(N+1):
  if dp[i] < 0:
    print(i-1)
    exit(0)

print(N)


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  h,p = list(map(int, input().split()))
  A.append([h+p,h,p])
  
A.sort()

# N人積んだ時の最小の高さH
dp = [-1 for i in range(N+1)]
dp[0] = 0

for i in range(N):
  _,h,p = A[i]
  for j in range(N, 0, -1):
    ## まだj-1人積んだことがない
    if dp[j-1] < 0:
      continue
    ## 高すぎてつめない
    if dp[j-1] > h:
      continue
    if dp[j] < 0:
      dp[j] = dp[j-1] + p
    else:
      dp[j] = min(dp[j], dp[j-1] + p)
    
for i in range(N+1):
  if dp[i] < 0:
    print(i-1)
    exit(0)

print(N)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC68 C

n,m = map(int,input().split())

s = []
g = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s.append(b)
    if b == n:
        g.append(a)
f = 0
for i in range(len(s)):
    if s[i] in g:
        f = 1
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


### FIXED CODE ###

#!/usr/bin/env python3
#ABC68 C

n,m = map(int,input().split())

s = [0]*(200000+1)
g = [0]*(200000+1)
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s[b] += 1
    if b == n:
        g[a] += 1
f = 0
for i in range(200000+1):
    if s[i] & g[i]:
        f = 1
        break
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')