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

import numpy as np
import bisect
N, M = map(int, input().split())
As = sorted(list(map(int, input().split())), reverse=True)
cards = np.array(As, dtype=np.int64) * -1

for i in range(M):
    B, C = map(int, input().split())

    p = bisect.bisect_right(cards, -C)
    if p >= N:
        continue

    replace = min(N - p, B)
    new_cards = np.array([-C]*replace, dtype=np.int64)
    cards = np.concatenate([cards[:p], new_cards,  cards[p:N-replace]])

total = 0
for card in cards:
    total += -card
print(total)

### FIXED CODE ###

import heapq
from collections import defaultdict

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

As = map(int, input().split())
counts = defaultdict(int)
for A in As:
    counts[A] += 1
h = sorted(counts.keys())

for i in range(M):
    B, C = map(int, input().split())

    if C not in counts:
        heapq.heappush(h, C)
    counts[C] += B
    if len(h) > N:
        v = heapq.heappop(h)
        del counts[v]

total_count = 0
total = 0
for k in sorted(h, reverse=True):
    c = counts[k]
    c = min(c, N - total_count)
    total += k * c
    total_count += c
    if total_count > N:
        break
print(total)
### BUGGY CODE ###

import sys
s = str(input())
Q = int(input())
cnt = 0

for i in range(Q):
  q = list(input().split())
  if q[0] == '1':
    cnt = (cnt+1) % 2
  elif q[1] == '1':
    if cnt == 0:
      s = q[2] + s
    else:
      s += q[2]
  else:
    if cnt == 0:
      s += q[2]
    else:
      s = q[2] + s

if cnt == 0:
  print(s)
else:
  print(s[::-1])

### FIXED CODE ###

from collections import deque
import sys
s = deque(list(input()))
Q = int(input())
cnt = 0

for i in range(Q):
  q = list(input().split())
  if q[0] == '1':
    cnt = (cnt+1) % 2
  elif q[1] == '1':
    if cnt == 0:
      s.appendleft(q[2])
    else:
      s.append(q[2])
  else:
    if cnt == 0:
      s.append(q[2])
    else:
      s.appendleft(q[2])

if cnt == 1:
  s.reverse()
print("".join(s))
### BUGGY CODE ###

import itertools
import copy

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

digit = [len(set(S[i+1:])) for i in range(N-1)]
ans = [0 for i in range(100)]
for i in range(N-2):
  for j in range(i+1, N-1):
    tmp = int(S[i])*10 + int(S[j])
    ans[tmp] = max(ans[tmp], (digit[j]))

print(sum(ans))


### FIXED CODE ###

n = int(input())
s = input()

count = 0
for i in range(1000):
  tmp = format(i, '03')
  k = 0
  for j in s:
    if j == tmp[k]:
      k+=1
    if k == 3:
      count+=1
      break
print(count)
### BUGGY CODE ###

A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

def bsearch_sub(a, v, imin, imax):
	if imax < imin:
		return (imax, imin)
	else:
		imid = imin + (imax - imin) // 2
		if v < a[imid]:
			return bsearch_sub(a, v, imin, imid - 1)
		elif a[imid] < v:
			return bsearch_sub(a, v, imid + 1, imax)
		else:
			return (imid, imid)

def bsearch(a, v):
	return bsearch_sub(a, v, 0, len(a) - 1)

#print(S, T)
for x in X:
	s = bsearch(S, x)
	sb, sd = [], []
	if 0 <= s[0] < A:
		sb += [S[s[0]]]
		sd += [S[s[0]] - x]
	if 0 <= s[1] < A:
		sb += [S[s[1]]]
		sd += [S[s[1]] - x]

	t = bsearch(T, x)
	tb, td = [], []
	if 0 <= t[0] < B:
		tb += [T[t[0]]]
		td += [T[t[0]] - x]
	if 0 <= t[1] < B:
		tb += [T[t[1]]]
		td += [T[t[1]] - x]

	r = []
	for sn in sd:
		for tn in td:
			if sn < 0 and tn < 0:
				r += [max([-sn, -tn])]
			elif 0 < sn and 0 < tn:
				r += [max([sn, tn])]
			else:
				r += [min([abs(sn), abs(tn)]) * 2 + max([abs(sn), abs(tn)])]
	print(min(r))

	#print(x, s, sb, sd)
	#print(x, t, tb, td)
	#print(x, bsearch(S, x), sb, bsearch(T, x), tb)


### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())

INF = 10 ** 11 + 1
S = [-INF] + [int(input()) for _ in range(A)] + [INF]
T = [-INF] + [int(input()) for _ in range(B)] + [INF]
X = [int(input()) for _ in range(Q)]

"""
def bsr(a, v, lo=0, hi=None):
	if hi == None:
		hi = len(a) - 1
	if hi < lo:
		return lo
	mi = (lo + hi) // 2
	if v < a[mi]:
		return bsr(a, v, lo, mi - 1)
	else:
		return bsr(a, v, mi + 1, hi)
"""

def bsr(a, v):
	return bisect.bisect_right(a, v)

#print(S)
#print(T)
#print()

for x in X:
	sr = bsr(S, x)
	sl = sr - 1
	tr = bsr(T, x)
	tl = tr - 1
	#print(sr, sl, tr, tl)
	#print(S[sr], S[sl], T[tr], T[tl])
	cost = []
	for m in [S[sr], S[sl]]:
		for n in [T[tr], T[tl]]:
			cost += [abs(x - m) + abs(m - n), abs(x - n) + abs(m - n)]
	#print(sr, sl, tr, tl, cost)
	print(min(cost))
	#break
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
for i in range(q):
    u,v=map(int,input().split())
    u-=1
    v-=1
    while u!=v:
        if u>v:
            if (u-1)//n>v:
                u=(u-1)//(n*n)
            else:
                u=(u-1)//n
        else:
            if (v-1)//n>v:
                v=(v-1)//(n*n)
            else:
                v=(v-1)//n
    print(u+1)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
for i in range(q):
    u,v=map(int,input().split())
    if n==1:
        print(min(u,v))
        continue
    u-=1
    v-=1
    while u!=v:
        if u>v:
            if (u-1)//n>v:
                u=(((u-1)//n)-1)//n
            else:
                u=(u-1)//n
        else:
            if (v-1)//n>v:
                v=(((v-1)//n)-1)//n
            else:
                v=(v-1)//n
    print(u+1)
### BUGGY CODE ###

def main():
    N = int(input())
    A = []
    d = []
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(i+1, N):
            if Ai[j] > 0:
                d.append((Ai[j], i, j))
    d.sort(key=lambda x: x[0])


    def wf(dist):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist


    ok = len(d)+1
    ng = 0
    mid = (ok+ng)//2
    while ok - ng > 1:
        dist = [[10 ** 10 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            dist[i][i] = 0
        for x, i, j in d[:mid]:
            dist[i][j] = x
            dist[j][i] = x
        if wf(dist) == A:
            ok = mid
        else:
            ng = mid
            if ng == len(d):
                print(-1)
                exit()
        mid = (ok+ng)//2

    ans = 0
    for i in range(ok):
        ans += d[i][0]
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = []
    dist = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(N):
            dist[i][j] = Ai[j]

    def wf(dist):
        need = [[1 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        print(-1)
                        exit()
                    elif dist[i][j] == dist[i][k] + dist[k][j]:
                        if i != k and j != k:
                            need[i][j] = 0
                            need[j][i] = 0
        return need

    need = wf(dist)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += need[i][j] * dist[i][j]
    print(ans)


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

import itertools
n, k = map(int, input().split())
a = []
x = k/2
count = 0
while x <= n:
    if x % 1 == 0:
        a.append(int(x))
    x += k/2
ori_list = list(itertools.product(a, repeat=3))
for i in range(len(ori_list)):
    if (ori_list[i][0] + ori_list[i][1]) % k == 0:
    	if (ori_list[i][1] + ori_list[i][2]) % k == 0:
    		if (ori_list[i][0] + ori_list[i][2]) % k == 0:
        		count += 1

print(count)

### FIXED CODE ###

n, k = map(int, input().split())
cnt = 0

if k % 2 == 1:
    for i in range(1, n+1):
        if i % k == 0:
            cnt += 1
    ans = cnt ** 3
elif k % 2 == 0:
    cnt1 = 0
    cnt2 = 0
    for i in range(1, n+1):
        if i % k == 0:
            cnt1 += 1
        elif i % k == k/2:
            cnt2 += 1
    ans = cnt1 ** 3 + cnt2 ** 3
print(ans)
### BUGGY CODE ###

from heapq import *
from collections import Counter
import itertools


n, x, y = map(int,input().split())
edges = [[] for _ in range(n)]

def dijkstra(s, edges):
    d = [float('inf')] * n
    d[s] = 0
    heap = [(0, s)]
    while heap:
        c, node = heappop(heap)
        for cost, v in edges[node]:
            if c + cost < d[v]:
                d[v] = c + cost
                heappush(heap, (d[v], v))
    return d

for i in range(n-1):
    u, v = i, i+1
    edges[u].append([1,v])
    edges[v].append([1,u])
edges[x-1].append([1, y-1])
edges[y-1].append([1, x-1])

ans = []

for s in range(n):
    ans.append(dijkstra(s, edges))

f_ans = []
for i in range(n):
    f_ans.append(ans[i][i+1:])
f_ans = list(itertools.chain.from_iterable(f_ans))
f_ans = Counter(f_ans)

for i in range(1, n):
    print(f_ans[i])

### FIXED CODE ###

n, x, y = map(int,input().split())
ls = [0] * n
for u in range(1, n):
    for v in range(u, n+1):
        u2x = abs(u-x)
        v2y = abs(v-y)

        d = min(v-u, u2x + 1 + v2y)
        ls[d] += 1

for k in range(1, n):
    print(ls[k])
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
rgb = [r,g,b]
rgb.sort()
x = rgb[2]
y = rgb[1]
z = rgb[0]
ans = 0

for i in range(n//x+30):
    for j in range(n//y+30):
        if (n-x*i-y*j)%z ==0:
            if (n-x*i-y*j)//z >=0:
                ans += 1
          
print(ans)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
rgb = [r,g,b]
rgb.sort()
x = rgb[2]
y = rgb[1]
z = rgb[0]
ans = 0

for i in range(n//x+30):
    for j in range(n//y+30):
        if (n-x*i-y*j)%z ==0:
            if (n-x*i-y*j)//z >=0:
                ans += 1
          
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = [[] for _ in range(N)]
    for i in range(N):
        A[i] = list(map(lambda x: int(x) - 1, input().split()))

    # print(A)

    days = 0
    while True:
        ta = []
        aset = set()
        for i in range(N):
            if len(A[i]) == 0 or i in aset:
                continue
            if i == A[A[i][0]][0]:
                ta.append(i)
                ta.append(A[i][0])
                aset |= set([i])
                aset |= set([A[i][0]])
        if len(ta) > 0:
            for t in ta:
                A[t].pop(0)
            days += 1
        else:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print(-1)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = [[] for _ in range(N)]
    for i in range(N):
        A[i] = list(map(lambda x: int(x) - 1, input().split()))

    # print(A)

    days = 0
    ta = [i for i in range(N)]
    while True:
        ta2 = []
        aset = set()
        for i in ta:
            if len(A[i]) == 0 or i in aset:
                continue
            if i == A[A[i][0]][0]:
                ta2.append(i)
                ta2.append(A[i][0])
                aset |= set([i])
                aset |= set([A[i][0]])
        if len(ta2) > 0:
            for t in ta2:
                A[t].pop(0)
            days += 1
            ta = ta2
        else:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print(-1)


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

import math
         
while 1:
    try:
        n = input()
        c = 0
        ps = [False for i in range(n)]
        for i in range(2, n):
            ps[i] = True
        for i in range(2, int(math.sqrt(n)+1)):
            if ps[i]:
                for j in range(i**2, n, i):
                    ps[j] = False
            
        for i in range(n):
            if ps[i] is True:
                c += 1
        print c
    except EOFError:
        break

### FIXED CODE ###

n = 10**6
c = 0
ps = [False]*(n+1)
for i in xrange(2, n+1):
    if i%2 != 0 or i == 2:
        ps[i] = True
for i in xrange(2, int(n**0.5+1)):
    if ps[i]:
        for j in xrange(i**2, n+1, i):
            ps[j] = False

while 1:
    try:
        n = input()
        if n == 2: print 1
        else: print len([0 for i in xrange(2, n+1) if ps[i]])
    except EOFError:
        break
### BUGGY CODE ###

import copy
import itertools
S = input()

K = 0
S__ = []

for i in reversed(range(len(S))):
    S_ = list(itertools.combinations(range(len(S) - 1), i))
    for j in S_:
        j = list(j)

        index = 0
        buff = ""
        S__ = []
        for k in range(len(S)):
            if index >= len(j):
                buff += S[k:]
                S__.append(buff)
                buff = ""
                break
            buff += S[k]

            if k == j[index]:
                S__.append(buff)
                buff = ""
                index += 1

        for k in range(len(S__) - 1):
            if S__[k] != S__[k+1]:
                if k == len(S__) - 2:
                    print(len(S__))
                    exit(0)
            else:
                break






    

### FIXED CODE ###

S = input()
ans = []

prev = ""
now = ""
for i in range(len(S)):
    now = now + S[i]
    if now != prev:
        ans.append(now)
        prev = now
        now = ""


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

n,k,q = map(int,input().split())
a = [int(input()) for i in range(q)]
a = sorted(a)
for i in range(1,n+1):
    if len(a) - a.count(i) >= k:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n,k,q = map(int,input().split())
p = [0]*n
for i in range(q):
    a = int(input())
    p[a-1] += 1

for i in range(n):
    if k > q - p[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

s = input()[::-1]
num = 0
last = 0
d = 1
count = [0] * 2019 # 余りの格納箱
count[0] =1  # 割り切れるとき
for i in s:
    num = int(i) * d + last
    last = num
    num %= 2019
    d *= 10
    count[num] += 1
    
ans = 0
for i in count:
    ans += i * (i-1) //2
print(ans)

### FIXED CODE ###

s = input()[::-1]
num = 0
last = 0
d = 1
count={}
for k in range(2019):
    count[k] = 0
    
count[0] =1  # 割り切れるとき

for i in s:
    num = (int(i) * d + num)%2019
    
    d *= 10
    d %= 2019
    count[num] += 1
    
ans = 0
for j in range(2019):
    ans += count[j] * (count[j]-1) //2
print(ans)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
ans = 1
light = 0
list = []

while True:
    if A[light] == 1:
        ans = -1
        break
    elif A[light] == 2:
        break
    else:
        ans = ans + 1
        light = A[light] - 1

print(ans)

### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
ans = 0
light = 1
list = [0] * n

while True:
    if light == 2:
        break
    elif list[light - 1] == 1:
        ans = -1
        break
    else:
        ans = ans + 1
        list[light - 1] = 1
        light = A[light - 1]

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

from collections import deque
n, m = map(int, input().split())
A = [0] * m
B = [0] * m
for i in range(m):
    A[i], B[i] = map(int, input().split())

next_queue = deque()
delete_items = deque()
sign = [-1] * n

next_queue.append(1)

while next_queue:
    current_number = next_queue.popleft()
    for i, _ in enumerate(A):
        if A[i] == current_number:
            if sign[B[i] - 1] == -1:
                sign[B[i] - 1] = current_number
                if B[i] != 1:
                    next_queue.append(B[i])
                delete_items.append(i)
        if B[i] == current_number:
            if sign[A[i] - 1] == -1:
                sign[A[i] - 1] = current_number
                if A[i] != 1:
                    next_queue.append(A[i])
                delete_items.append(i)
    for i in sorted(list(delete_items), reverse=True):
        A.pop(i)
        B.pop(i)
    delete_items.clear()
print("Yes")
for i in range(1, n):
    print(sign[i])




### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
route = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    route[a-1].append(b - 1)
    route[b-1].append(a - 1)

next_queue = deque()
sign = [-1 for i in range(n)]
sign[0] = 999

next_queue.append(0)

while next_queue:
    current_number = next_queue.popleft()
    for room in route[current_number]:
        if sign[room] == -1:
            sign[room] = current_number
            next_queue.append(room)
print("Yes")
for i in range(1, n):
    print(sign[i] + 1)
### BUGGY CODE ###

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

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

sl = deque()
ans = 0
pen = 0
WA = [0 for _ in range(N)]
for i in range(M):
    p, S = input().split()
    if p in sl:
        continue

    if S == 'AC':
        ans += 1
        sl.append(p)
        pen += WA[int(p) - 1]
    else:
        WA[int(p) - 1] += 1

print(ans, pen)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

sl = set()
ans = 0
pen = 0
WA = [0 for _ in range(N)]
for i in range(M):
    p, S = input().split()
    if p in sl:
        continue

    if S == 'AC':
        ans += 1
        sl.add(p)
        pen += WA[int(p) - 1]
    else:
        WA[int(p) - 1] += 1

print(ans, pen)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
MOD = 10 ** 9 + 7
A_bin = list(map(lambda x: bin(x)[2:].zfill(60), A))
zero = [0] * 60
one = [0] * 60

for num in A_bin:
    for digit in range(60):
        if num[-(digit + 1)] == '0':
            zero[digit] += 1
        else:
            one[digit] += 1

for digit in range(60):
    ans += ((zero[digit] * one[digit])  * pow(2, digit, MOD)) % MOD
    ans %= MOD

print(ans)


### FIXED CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
ans = 0
MOD = 10 ** 9 + 7

for digit in range(60):
    one = np.count_nonzero((A >> digit) & 1)
    ans += (one * (N - one) * pow(2, digit, MOD)) % MOD
    ans %= MOD

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

import sys
sys.setrecursionlimit(10 ** 6)

N, Q = map(int, input().split())
AB = [[] for i in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    AB[a].append(b)

X = [0] * (N + 1)
for _ in range(Q):
    p, x = map(int, input().split())
    X[p] += x


def dfs(p):
    for c in AB[p]:
        X[c] += X[p]
        dfs(c)


dfs(1)
print(" ".join(map(str, X[1:])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)


N, Q = map(int, input().split())
AB = [[] for i in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    AB[a].append(b)

X = [0] * (N + 1)
for _ in range(Q):
    p, x = map(int, input().split())
    X[p] += x


def recursive(p):
    for c in AB[p]:
        X[c] += X[p]
        recursive(c)


recursive(1)
print(" ".join(map(str, X[1:])))
### BUGGY CODE ###

def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N, M = LI()
    A = LI()
    A.sort()
    l = 0; r = max(A)*2+1
    while(r-l>1):
        now = (l+r)//2
        cnt = 0
        for i in range(N):
            need = now-A[i]
            c = bisect.bisect_left(A,need)
            cnt += N-c
        if cnt>=M:
            l = now
        else:
            r = now
    base = l
    cnt = 0
    ans = 0
    for i in range(N):
        need = base - A[i]
        c = bisect.bisect_left(A, need+1)
        for j in range(c,N):
            ans += A[i]+A[j]
            cnt += 1
    if cnt<M:
        ans += base*(M-cnt)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

### FIXED CODE ###

def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N, M = LI()
    A = LI()
    A.sort()
    ma = max(A)
    l = 0; r = ma*2+1
    while(r-l>1):
        now = (l+r)//2
        cnt = 0
        for a in A:
            need = now-a
            if need>ma:
                continue
            c = bisect.bisect_left(A,need)
            cnt += N-c
        if cnt>=M:
            l = now
        else:
            r = now
    base = l
    cnt = 0
    ans = 0
    S = [0]+A
    for i in range(N):
        S[i+1] += S[i]
    #print(S)
    for a in A:
        need = base - a
        c = bisect.bisect_left(A, need+1)
        ans += a*(N-c) + S[N]-S[c]
        cnt += (N-c)
    if cnt<M:
        ans += base*(M-cnt)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import itertools

def main():
    n, k = map(int, input().split())

    n_li = list(range(n+1))

    ans = 0

    for i in range(k, n+2):
        ans += len(set(list(map(sum, list(itertools.combinations(n_li,i))))))

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    MOD = 1000000007
    n, k = map(int, input().split())

    n_li = list(range(n+1))

    ans = 0

    while(k <= n+1):
        p = (k - 1) * k / 2
        q = ((n + n - k + 1) * k) / 2

        ans += q - p + 1
        ans %= MOD
        k += 1

    print(int(ans))

if __name__ == '__main__':
    main()