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

def upd(a, b, v):
    global N
    dp[a][b] = max(dp[a][b], v)
    dp[b][a] = max(dp[b][a], v)
    dp[N][a] = max(dp[N][a], v)
    dp[N][b] = max(dp[N][b], v)
    dp[a][N] = max(dp[a][N], v)
    dp[b][N] = max(dp[b][N], v)
    dp[N][N] = max(dp[N][N], v)


N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))

INF = 1 << 32
dp = [[-INF] * (N + 1) for _ in range(N + 1)]
upd(A[0], A[1], 0)
base = 0
q = [None] * (3 * N + 3)

for i in range(2, 3 * N - 1, 3):
    x, y, z = A[i], A[i + 1], A[i + 2]
    if x == y == z:  # x, y, z 3文字すべて等しいとき
        base += 1
    else:
        cur = 0
        for _ in range(3):
            # a, b, x, y, z のうち, b, y, z を消すとき
            for k in range(N):
                v = dp[k][N]
                if y == z:
                    v = max(v, dp[k][y] + 1)
                q[cur] = (k, x, v)
                cur += 1
            # a, b, x, y, z のうち, a, b, z を消すとき
            v = max(dp[z][z] + 1, dp[N][N])
            q[cur] = (x, y, v)
            cur += 1
            # x, y, z をローテート
            x, y, z = z, x, y
        for j in range(cur):
            upd(*q[j])

l = A[-1]
ans = max(dp[N][N], dp[l][l] + 1)
print(ans + base)


### FIXED CODE ###

from collections import deque


def upd(a, b, v):
    global N
    dp[a][b] = max(dp[a][b], v)
    dp[b][a] = max(dp[b][a], v)
    dp[N][a] = max(dp[N][a], v)
    dp[N][b] = max(dp[N][b], v)
    dp[a][N] = max(dp[a][N], v)
    dp[b][N] = max(dp[b][N], v)
    dp[N][N] = max(dp[N][N], v)


N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))

INF = 1 << 32
dp = [[-INF] * (N + 1) for _ in range(N + 1)]
upd(A[0], A[1], 0)
base = 0

for i in range(2, 3 * N - 1, 3):
    x, y, z = A[i], A[i + 1], A[i + 2]
    if x == y == z:  # x, y, z 3文字すべて等しい
        base += 1
    else:
        q = deque()
        for _ in range(3):
            for k in range(N):
                v = dp[k][N]
                if y == z:
                    v = max(v, dp[k][y] + 1)
                q.append((k, x, v))
            v = max(dp[z][z] + 1, dp[N][N])
            q.append((x, y, v))
            x, y, z = z, x, y
        while q:
            a, b, v = q.popleft()
            upd(a, b, v)

l = A[-1]
ans = max(dp[N][N], dp[l][l] + 1)
print(ans + base)
### BUGGY CODE ###

mi = lambda : map(int, input().split())

l, r = mi()

ans = 2018
for i in range(l, r+1):
    for j in range(l, r+1):
        if i<j and ans>(i*j)%2019:
            ans = (i*j)%2019
print(ans)

### FIXED CODE ###

mi = lambda : map(int, input().split())

l, r = mi()

if r-l>2019:
    r = l+2019

ans = 2018
for i in range(l, r+1):
    for j in range(l, r+1):
        if i<j and ans>(i*j)%2019:
            ans = (i*j)%2019
print(ans)
### BUGGY CODE ###

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

import itertools


def mostProperComb(childs, x):
    tmp_sum = sum([c[1] for c in childs])
    if tmp_sum > x:
        print("IMPOSSIBLE")
        exit()

    total = tmp_sum + sum([c[0] for c in childs])

    max_a, min_b = 0, 0
    for code in itertools.product([False, True], repeat=len(childs)):
        a = 0
        for j, bool in enumerate(code):
            if bool:
                a += childs[j][1]
            else:
                a += childs[j][0]
            if a > x:
                break
        if a >= max_a and x >= a:
            max_a, min_b = a, total - a
            if max_a == x:
                break

    return (tuple(sorted([x, min_b], reverse=True)))


n = int(input())

p_list = [0] + list(map(int, input().split()))
x_list = list(map(int, input().split()))
c_list = [[] for i in range(n)]

if n == 1:
    print("POSSIBLE")
    exit()

for i in range(n):
    index = n - 1 - i

    if len(c_list[index]) == 0:
        c_list[index] = (x_list[index], 0)
        c_list[p_list[index] - 1].append(index)
    else:
        childs = [c_list[child_index] for child_index in c_list[index]]
        c_list[index] = mostProperComb(childs, x_list[index])
        if not p_list[index] == 0:
            c_list[p_list[index] - 1].append(index)

print("POSSIBLE")


### FIXED CODE ###

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

import itertools


def mostProperComb(childs, x):
    tmp_sum = sum([c[1] for c in childs])
    if tmp_sum > x:
        print("IMPOSSIBLE")
        exit()

    total = tmp_sum + sum([c[0] for c in childs])

    sset = set([tmp_sum])
    for child in childs:
        rest = child[0] - child[1]
        tmp_set = set(sset)
        for s in sset:
            if s + rest <= x:
                tmp_set.add(s+rest)
        sset = tmp_set

    return (tuple(sorted([x, total-max(sset)], reverse=True)))


n = int(input())

p_list = [0] + list(map(int, input().split()))
x_list = list(map(int, input().split()))
c_list = [[] for i in range(n)]

if n == 1:
    print("POSSIBLE")
    exit()

for i in range(n):
    index = n-1-i

    if len(c_list[index]) == 0:
        c_list[index] = (x_list[index], 0)
        c_list[p_list[index]-1].append(index)
    else:
        childs = [c_list[child_index] for child_index in c_list[index]]
        c_list[index] = mostProperComb(childs, x_list[index])
        if not p_list[index] == 0:
            c_list[p_list[index]-1].append(index)

print("POSSIBLE")
### BUGGY CODE ###

a, b, k = map(int,input().split())
for i in range(k):
    if a >= 1:
        a -= 1
        
        
    
        if a == 0 and b >= 1:
            b -= 1
            if b == 0:
                exit()
    
print(str(a) + " " + str(b))

### FIXED CODE ###

a, b, k = map(int, input().split())
if k < a:
    print(str(a - k) + " " + str(b))
elif a <= k and k < a + b:
    print(str(0) + " " + str(b - k + a))
elif k >= a + b:
    print(str(0) + " " + str(0))
### BUGGY CODE ###

def abc097_c():
    S = str(input())
    K = int(input())
    pos = dict()
    subs = set()

    for i, c in enumerate(S):
        if pos.get(c):
            pos[c].append(i)
        else:
            pos[c] = [i]

    keys = sorted(list(pos.keys()))
    for c in keys:
        for st in pos[c]:
            for ed in range(st+1, len(S)+1):
                subs.add(S[st:ed])
        if len(subs) >= K:
            break

    ans = sorted(list(subs))[K-1]
    print(ans)

abc097_c()

### FIXED CODE ###

def abc097_c():
    S = str(input())
    K = int(input())
    subs = set()

    for i in range(len(S)):
        for j in range(i+1, min(len(S)+1, i+K+1)):
            subs.add(S[i:j])

    subs_asc = sorted(list(subs))
    ans = subs_asc[K-1]
    print(ans)

abc097_c()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

hor = [0] * H
ver = [0] * W
f = [[0 for _ in range(W)] for _ in range(H)]
for _ in range(m):
    h, w = map(int, input().split())
    hor[h - 1] += 1
    ver[w - 1] += 1
    f[h - 1][w - 1] = 1

hs = []
hmax = max(hor)
for i, v in enumerate(hor):
    if hmax == v:
        hs.append(i)
vs = []
vmax = max(ver)
for i, v in enumerate(ver):
    if vmax == v:
        vs.append(i)

ans = hmax + vmax
for k1 in hs:
    for k2 in vs:
        if f[k1][k2] == 0:
            print(ans)
            exit()
print(ans - 1)


### FIXED CODE ###

import sys
from collections import defaultdict

input = sys.stdin.readline

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

hor = [0] * H
ver = [0] * W
f = defaultdict(int)
for _ in range(m):
    h, w = map(int, input().split())
    hor[h - 1] += 1
    ver[w - 1] += 1
    f[str(h - 1) + '|' + str(w - 1)] = 1

hmax = max(hor)
hs = [i for i, v in enumerate(hor) if v == hmax]
vmax = max(ver)
vs = [i for i, v in enumerate(ver) if v == vmax]


ans = hmax + vmax

if len(hs) * len(vs) > m:
    print(ans)
    exit()

for k1 in hs:
    for k2 in vs:
        if f[str(k1) + '|' + str(k2)] == 0:
            print(ans)
            exit()
print(ans - 1)
### BUGGY CODE ###

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

for i in range(k):
  if (a+b) == 0:
    break
  if a >= 1:
    a -= 1
  else:
    b -= 1
print(a, b)

### FIXED CODE ###

from sys import exit
a, b, k = map(int, input().split(" "))


if (a+b) <= k:
    print(0,0)
    exit()
    
a -= k

if a <= 0:
    b += a
    a = 0
print(a, b)
### BUGGY CODE ###

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

ans=-1
for i in range(1,n+1):
    if i in renga:
        idx=renga.index(i)
        renga=renga[idx+1:]
        ans=i
        continue
    else:
        break

if ans!=-1:
    ans=n-ans

print(ans)

### FIXED CODE ###

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

ans=-1
inf=0
for i in range(1,n+1):
    flag=0
    for j in range(inf,n):
        if renga[j]==i:
            ans=i
            inf=j+1
            flag=1
            break
    if flag==0:
        break

if ans!=-1:
    ans=n-ans

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

a,b=map(int,input().split())
l=list(map(int,input().split()))
for i in range(min(b,int(a**0.5)+4)):
  now=[0]*a
  for j in range(a):
    x=l[j]
    for k in range(max(0,j-x),min(a,j+x+1)):
      now[k]+=1
  l=now
for i in range(a):
  now[i]=min(now[i],a)
print(*now)


### FIXED CODE ###

a,b=map(int,input().split())
l=list(map(int,input().split()))
import itertools
b=min(b,50)
def ku(l):
    y=[0]*a
    for j,x in enumerate(l):
      y[max(0,j-x)]+=1
      r=min(j+x,a-1)
      if r<a-1:
        y[r+1]-=1
    return itertools.accumulate(y)

  
for _ in range(b):
  l=ku(l)
print(*l)
### BUGGY CODE ###

S = list(input())
count = 0

for i in range(len(S)-3):
    for j in range(i+4, len(S)+1):
        num = int(''.join(S[i:j]))
        if num % 2019 == 0:
            count += 1

print(count)



### FIXED CODE ###

S = list(input())[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1  # If 2019 is exist, count number
current = 0
x = 1
for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current]
    mods[current] += 1
    x = x * 10 % 2019

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

import collections

N, M = map(int, input().split())
WA_CNT = []
CLEAR = []
for i in range(M):
    P, S = input().split()
    P = int(P)
    if P in CLEAR:
        continue
    if S == "AC":
        CLEAR.append(P)
        continue

    WA_CNT.append(P)


cs = collections.Counter(WA_CNT)
num = len(CLEAR)
try_num = 0

for i in CLEAR:
    try_num += cs[i]
print("{} {}".format(num, try_num))

### FIXED CODE ###

import collections

N, M = map(int, input().split())
WA_CNT = {}
CLEAR = {}
for i in range(M):
    P, S = input().split()
    if P in CLEAR:
        continue
    if S == "AC":
        CLEAR[P] = 1
        continue

    if not P in WA_CNT:
        WA_CNT[P] = 0
    WA_CNT[P] += 1


num = len(CLEAR)
try_num = 0
for i in CLEAR:
    if i in WA_CNT:
        try_num += WA_CNT[i]
print("{} {}".format(num, try_num))
### BUGGY CODE ###

MOD = 10 ** 9 + 7

N, A, B = map(int, input().split())

tmp1 = pow(2, N, MOD) - 1 #1本以上の選び方

def combination(n, r): #nCrを求める
    if n - r > r:
        r = n - r
    tmp1 = 1
    for i in range(n - r + 1, n + 1):
        tmp1 *= i
        tmp1 %= MOD
    
    tmp2 = 1
    for i in range(1, r + 1):
        tmp2 *= i
        tmp2 %= MOD
    return tmp1 * pow(tmp2, MOD - 2, MOD)

tmp2 = combination(N, A)
tmp3 = combination(N, B)

print ((tmp1 - tmp2 - tmp3) % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7

N, A, B = map(int, input().split())

tmp1 = pow(2, N, MOD) - 1 #1本以上の選び方

#計算量 log(m)くらい
def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u


def combination(n, r): #nCrを求める
    if n - r < r:
        r = n - r
    tmp1 = 1
    for i in range(n - r + 1, n + 1):
        tmp1 *= i
        tmp1 %= MOD
    tmp2 = 1
    for i in range(1, r + 1):
        tmp2 *= i
        tmp2 %= MOD
    return tmp1 * modinv(tmp2, MOD)

tmp2 = combination(N, A)
tmp3 = combination(N, B)

print ((tmp1 - tmp2 - tmp3) % MOD)
### BUGGY CODE ###

def takeSecond(elem):
    return elem[1]

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

sushi = [list(map(int,input().split())) for i in range(n)]

sushi.sort(key=takeSecond,reverse=True)

selected = sushi[:k]
kindset = set([item[0] for item in selected])

startKindNum = len(kindset)

score = startKindNum*startKindNum + sum([item[1] for item in selected])
maxscore = score
front_pointer = k - 1
pointer = k
for i in range(startKindNum+1,min([k+1,n+1])):
    #remove the smallest one that does not decrease kind
    for p in range(front_pointer,-1,-1):
        item = selected[p]
        flag = False
        for idx in range(p):
            if(selected[idx][0]==item[0]):
                score -= item[1]
                selected.remove(item)
                front_pointer = p - 1
                flag = True
                break
        if(flag):
            break

    #add the largest one that add kind
    for j in range(pointer,n):
        if(sushi[j][0] not in kindset):
            selected.append(sushi[j])
            kindset.add(sushi[j][0])
            k += 1
            pointer = j + 1            
            score += 2*startKindNum + 1 + sushi[j][1]
            if(score>maxscore):
                maxscore = score
            startKindNum += 1
            break
print(maxscore)

### FIXED CODE ###

def takeSecond(elem):
    return elem[1]

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

sushi = [list(map(int,input().split())) for i in range(n)]

sushi.sort(key=takeSecond,reverse=True)
'''
selected = sushi[:k]
kindset = set([item[0] for item in selected])

startKindNum = len(kindset)

score = startKindNum*startKindNum + sum([item[1] for item in selected])
maxscore = score
front_pointer = k - 1
pointer = k
for i in range(startKindNum+1,min([k+1,n+1])):
    #remove the smallest one that does not decrease kind
    for p in range(front_pointer,-1,-1):
        item = selected[p]
        flag = False
        for idx in range(p):
            if(selected[idx][0]==item[0]):
                score -= item[1]
                selected.remove(item)
                front_pointer = p - 1
                flag = True
                break
        if(flag):
            break

    #add the largest one that add kind
    for j in range(pointer,n):
        if(sushi[j][0] not in kindset):
            selected.append(sushi[j])
            kindset.add(sushi[j][0])
            k += 1
            pointer = j + 1            
            score += 2*startKindNum + 1 + sushi[j][1]
            if(score>maxscore):
                maxscore = score
            startKindNum += 1
            break
'''
kindset = set([])
score = 0
extras = []
for item in sushi[:k]:
    if item[0] in kindset:
        extras.append(item[1])
    else:
        kindset.add(item[0])
    score += item[1]
score += len(kindset)**2
maxscore = score
for item in sushi[k:]:
    if not  extras:
        break
    if item[0] in kindset:
        continue
    score += (item[1] - extras.pop()) + 2*len(kindset) + 1
    kindset.add(item[0])
    #print(score)
    if score > maxscore:
        maxscore = score


print(maxscore)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
def __main__():
    ans = 1
    for i in a:
        ans *= i
    if(ans > 10**18):
        print(-1)
        return
    print(ans)
    return

if(__name__=="__main__"):
    __main__()

### FIXED CODE ###

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

def __main__():
    ans = 1
    if(0 in a):
        print(0)
        return
    else:
        for i in a:
            ans *= i
            if(ans > 10**18):
                print(-1)
                return
        print(ans)
        return

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

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

import sys

def main():
    n = int(input())
    ans=[0]*n
    count=0

    for i in range(1,n+1):
        for x in range(1,n):
            if x**2 >= i:
                break
            for y in range(1,n):
                for z in range(1,n):
                    if x**2+y**2+z**2+x*y+y*z+z*x==i:
                        count+=1
        print(count)
        count=0

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

import sys
import math

def main():
    n = int(input())
    root_n=math.ceil(math.sqrt(n))
    ans=[0]*n
    count=0

    for x in range(1,root_n):
        for y in range(1,root_n):
            for z in range(1,root_n):
                tmp=x**2+y**2+z**2+x*y+y*z+z*x
                if tmp<n+1:
                    ans[tmp-1]+=1
    for i in ans:
        print(i)

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

from collections import deque
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = {i:[] for i in range(N)}
X = [0]*(N)
searched = [0]*(N)
pairents = [-1]*N

for _ in range(N-1+M):
    a, b = inpl()
    G[a-1].append(b-1)
    X[b-1] += 1

q = X.index(0)

Q = deque([q])
while Q:
    p = Q.popleft()
    for q in G[p]:
        if searched[q] <= searched[p]:
            searched[q] = searched[p] + 1
            Q.append(q)

for a in range(N):
    for b in G[a]:
        if searched[b] == searched[a] + 1:
            pairents[b] = a
for p in pairents:
    print(p+1)
    


### FIXED CODE ###

from collections import deque
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = {i:[] for i in range(N)}
rG = {i: [] for i in range(N)}
X = [0]*(N)
searched = [0]*(N)

for _ in range(N-1+M):
    a, b = inpl()
    G[a-1].append(b-1)
    rG[b-1].append(a-1)
    X[b-1] += 1

q = X.index(0)
T = [0]*N
Q = deque([q])
t = 0
while Q:
    p = Q.popleft()
    T[p] = t
    t += 1
    for q in G[p]:          
        X[q] -= 1
        if X[q] == 0:
            Q.append(q)

for i in range(N):
    c, ans = -1, 0
    for p in rG[i]:
        if c < T[p]:
            c, ans = T[p], p+1
    print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0 for _ in range(13)]for _ in range(length+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

	for i in range(1,length):
		if s[-i-1] != '?':
			num = (int(s[-i-1]) * (10**i)) % 13
			for j in range(13):
				dp[i+1][j] = dp[i][(13-num+j)%13]
				dp[i+1][j] %= MOD
		else:
			num = (10**i) % 13
			a = 0
			for j in range(10):
				for k in range(13):
					dp[i+1][k] += dp[i][(13-a+k)%13]
					dp[i+1][k] %= MOD
				a += num

	print(dp[length][5] % MOD)

if __name__ == '__main__':
	main()

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

import sys

line = sys.stdin.readline()
x, y = line.split(" ")

x = int(x)
y = int(y)

divide = 1

if x > y:
    x, y = y, x

while(y % x != 0):
    for i in range(2, x + 1):
        if x % i == 0 and y % i == 0:
            divide = divide * i
            x = x / i
            y = y / i
            break

print divide

### FIXED CODE ###

import sys

def div(x, y):
    if x % y == 0:
        print y
    else:
        div(y, x%y)


line = sys.stdin.readline()
x, y = line.split(" ")

x = int(x)
y = int(y)

if x < y:
    x, y = y, x

if x == y:
    print x

else:
    div(x, y)
### BUGGY CODE ###

import math
N = int(input())

A = list(map(int, input().split()))
heikin = round(sum(A) / N) - 1

for i in range(N):
    A[i] = A[i] - heikin - i

s = []
t = []

absmax = max(list(map(abs, A)))

for i in range(-absmax - 1  , absmax + 1):
    t = []
    for j in range(N):
        t.append(abs(A[j] +  i))
    s.append(sum(t))

print(min(s))

### FIXED CODE ###

import statistics
import math

N = int(input())

A = list(map(int, input().split()))
A = [A[i] - i for i in range(N)]
med = round(statistics.median(A))

s0 = sum([abs(A[i] - med) for i in range(N)])
s1 = sum([abs(A[i] - med -1) for i in range(N)])
s2 = sum([abs(A[i] - med + 1) for i in range(N)])

print(min(s0, s1, s2))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def dp(i):
  for a,b in AB:
    C[i]=min(C[i],C[i-a if i>a else 0]+b)

H,N=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]
C=[0]+[10**8]*H

for i in range(1,H+1):
  dp(i)

print(C[H])


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  def dp(i):
    for a,b in AB:
      T=C[i-a if i>a else 0]+b
      C[i]=T if T<C[i] else C[i]

  H,N=map(int,input().split())
  AB=[list(map(int,input().split())) for _ in range(N)]
  C=[0]+[10**8]*H

  for i in range(1,H+1):
    dp(i)

  print(C[H])

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

n = int(input())
a = list(map(int,input().split()))
 
from fractions import gcd
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
 
ans=0
for i in a:
    ans+=lcm//i
 
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
 
from fractions import gcd
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
 
ans=0
for i in range(n):
    ans+=lcm//a[i]
 
print(ans%(10**9+7))
### BUGGY CODE ###

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

ans = 0
Ns = range(N+1)
MOD = 10**9 + 7

for i in range(K, N+2): #k-->N+1
    tmp = sum(Ns[-i:]) - sum(Ns[:i]) + 1
    ans += tmp
    ans %= MOD

print(ans)

### FIXED CODE ###

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

ans = 0
Ns = list(range(N+1))
cumsum = [0]
for i in range(N+1):
    cumsum.append(cumsum[i] + Ns[i])

MOD = 10**9 + 7

for i in range(K, N+2): #k-->N+1
    tmp = cumsum[-1] - cumsum[-i-1] - cumsum[i] + cumsum[0] + 1
    ans += tmp
    ans %= MOD

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

inp = input().split(" ")
N = int(inp[0])
K = int(inp[1])

arr = []
indicies = [0]

for i in range(N):
	inp = input().split(" ")
	a = int(inp[0])
	b = int(inp[1])
	if len(arr) == 0 or a >= arr[-1]:
		arr += [a] * b
		indicies.append(len(arr))
	elif a <= arr[0]:
		arr = ([a] * b) + arr
		for i in range(len(indicies)):
			indicies[i] += b
		indicies.append(0)
	else:
		index = 0
		for i in range(len(indicies)):
			i = indicies[i]
			if a >= arr[i-1] and a <= arr[i]:
				index = i
				
				arr = arr[0:i] + ([a] * b) + arr[i:]
				break
		for i in range(len(indicies)):
			if indicies[i] > index:
				indicies[i] += b
		indicies.append(index+b)

print(arr[K-1])


### FIXED CODE ###

x = raw_input().split(" ")
num_operations = int(x[0])
kth_integer = int(x[1])
field = {}
for p in range(0, num_operations):
 line = raw_input().split(" ")
 a = int(line[0])
 b = int(line[1])
 if a in field:
  field[a] += b
 else:
  field[a] = b
ks = field.keys()
ks.sort()
out = field.keys()[-1]
for k in ks:
 kth_integer -= field[k]
 if (kth_integer <= 0):
  out = k
  break
print (out)
### BUGGY CODE ###

'''
ワーシャルフロイド法
例題:https://atcoder.jp/contests/abc073/tasks/abc073_d
'''

N, M, R = map(int, input().split())
r = list(map(lambda x:int(x) - 1, input().split()))

dist = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
	tmp = list(map(int, input().split()))
	dist[tmp[0] - 1][tmp[1] - 1] = dist[tmp[1] - 1][tmp[0] - 1] = tmp[2]

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

ans = float('inf')
seen = []
def DFS():
	global ans
	for i in range(len(r)):
		if r[i] not in seen:
			seen.append(r[i])
			if len(seen) == len(r):
				sumDist = 0
				for j in range(len(seen) - 1):
					sumDist += dist[seen[j]][seen[j+1]]
				ans = min(ans, sumDist)
			else:
				DFS()
			del seen[-1]

DFS()
print(ans)

### FIXED CODE ###

import itertools
 
N, M, R = map(int, input().split())
r = [int(x) - 1 for x in input().split()]
 
dist = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
	a, b, c = map(int, input().split())
	a -= 1
	b -= 1
	dist[a][b] = dist[b][a] = c
 
for k in range(N):
	for i in range(N):
		for j in range(N):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
ans = float('inf')
k = list(itertools.permutations(r))
for i in k:
	sumDist = 0
	for j in range(len(i) - 1):
		sumDist += dist[i[j]][i[j+1]]
	ans = min(ans, sumDist)
print(ans)