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

import itertools

n = int(input())
xy = []
xyz =[]
a_list = []
ans = ['None']*n
count_list = []
count = 0
for _ in range(n):
    a = int(input())
    a_list.append(a)
    for i in range(a):
        x,y = map(lambda x: int(x),input().split())
        xy.append([x,y])
    xyz.append(xy)
    xy = []
xyz_all = list(itertools.permutations(xyz))

for i in range(len(list(itertools.permutations(xyz)))):
    for j in range(n):
        for k in range(a_list[j]) :
            hoge = xyz_all[i][j][k][:]
            if ans[hoge[0]-1] == 'None':
                ans[hoge[0]-1] = hoge[1]
            elif ans[hoge[0]-1] != hoge[1]:
                count+= 1
    count_list.append(count)



if ans == [0]*n :
    print(1)
else:
    print(n - min(count_list))


### FIXED CODE ###

import itertools


n = int(input())

all = list(itertools.product([0,1], repeat=n))
xy,xyz = [],[]
for _ in range(n):
    a = int(input())
    for i in range(a):
        x,y = map(lambda x: int(x),input().split())
        xy.append([x,y])
    xyz.append(xy)
    xy = []


test = ['None']*n
ans = []
ans_list = []
j_list = []
bool = True
hoge = 0
for i in range(len(all)):
    for j,k in enumerate(all[len(all) - 1 - i]):
        if k == 1:
            ans.append(xyz[j])
            j_list.append(j)
    ans = list(itertools.chain.from_iterable(ans))

    test = all[len(all) - 1 - i]
    for x in range(len(ans)):
        if test[ans[x][0]-1] != ans[x][1]:
            bool = False
            break

    if bool :
        hoge = all[len(all) - 1 - i]
        break
    bool = True
    test = ['None']*n
    ans = []
    j_list = []
print(sum(hoge))
### BUGGY CODE ###

n=input()
l=list(map(int, input().split()))
res=0
#print(f"le{len(l)}")
for i in range(len(l)):
    for j in range(i+1,len(l)):
        res+=l[i]*l[j]
        #print(res)
print(res%(10**9+7))

### FIXED CODE ###

import numpy
n=int(input())
l=list(map(int, input().split()))
res=0
mod=10**9+7
l.append(0)
l.reverse()
cum=numpy.cumsum(l)%mod
for i in range(n):
    res+=((l[n-i]%mod)*cum[n-i-1])%mod
print(res%mod)
### BUGGY CODE ###

def main():
    X, K, D = map(int, input().split())

    val = [0] * 100000000
    val[0] = X
    #val = X
    #val_new = 0
    if K % 2 == 0 :
        limit = 10
    else :
        limit = 11
    i = 0
    if abs(X) > K * D :
        if X > 0 :
            print(X - K * D)
        else :
            print(abs(X + K * D))
    elif X == K * D :
        print("0")
    else :
        for j in val :
            #print(i)
            if abs(val[i] - D) < abs(val[i] + D) :
                val[i+1] = val[i] - D
            else :
                val[i+1] = val[i] + D
            if (val[i+1] == val[i-1]) and i > limit :
                print(abs(val[i + 1]))
                break
            i += 1
            if i == K :
                print(abs(val[i]))
                break


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    X, K, D = map(int, input().split())

    val = [0] * 100000000
    val[0] = X
    #val = X
    #val_new = 0
    if K % 2 == 0 :
        limit = 4
    else :
        limit = 5
    i = 0
    if abs(X) > K * D :
        if X > 0 :
            print(X - K * D)
        else :
            print(abs(X + K * D))
    elif abs(X) == K * D :
        print("0")
    elif X == 0 :
        if limit == 4 :
            print('0')
        else :
            print(abs(D))
    else :
        syo = abs(X) // D
        #print(syo)
        if syo > 3 :
            if X > 0 :
                val[0] = X - (syo-2) * D
            else :
                val[0] = X + (syo - 2) * D
            #print(val[0])
            K = K -(syo-2)
            if K % 2 == 0:
                limit = 2
            else:
                limit = 3
        for j in val :
            #print(i)
            if abs(val[i] - D) < abs(val[i] + D) :
                val[i+1] = val[i] - D
            else :
                val[i+1] = val[i] + D
            #print(val[i+1])
            if (abs(val[i+1]) == abs(val[i-1])) and i > limit :
                #print("a")
                print(abs(val[i + 1]))
                break
            i += 1
            if i == K :
                #print("b")
                print(abs(val[i]))
                break


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

def main():
	n, m, *L = map(int, open(0).read().split())
	AB = L[:2 * m]
	Q = L[2 * m + 1:][::-1]
	G = [[] for _ in range(n)]
	C = [0] * n
	D = [-1] * n
	for a, b in zip(*[iter(AB)] * 2):
		a -= 1
		b -= 1
		G[a] += [b]
		G[b] += [a]
	for c, d, v in zip(*[iter(Q)] * 3):
		q = [(v - 1, d)]
		while q:
			cur, dd = q.pop()
			D[cur] = dd
			if not C[cur]:
				C[cur] = c
			if not dd:
				continue
			for nxt in G[cur]:
				if D[nxt] >= dd:
					continue
				q.append((nxt, dd - 1))
	print("\n".join(map(str, C)))

if __name__=="__main__":
	main()


### FIXED CODE ###

def main():
	n, m, *L = map(int, open(0).read().split())
	AB = L[:2 * m]
	Q = L[2 * m + 1:][::-1]
	G = [[] for _ in range(n)]
	C = [0] * n
	D = [-1] * n
	for a, b in zip(*[iter(AB)] * 2):
		a -= 1
		b -= 1
		G[a] += [b]
		G[b] += [a]
	for c, d, v in zip(*[iter(Q)] * 3):
		if D[v - 1] >= d:
			continue
		D[v - 1] = d
		q = [v - 1]
		while q:
			cur = q.pop()
			dd = D[cur]
			if not C[cur]:
				C[cur] = c
			if not dd:
				continue
			for nxt in G[cur]:
				if D[nxt] >= dd - 1:
					continue
				D[nxt] = dd - 1
				q.append(nxt)
	print("\n".join(map(str, C)))

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

S = input()
len_s = len(S)
while(True):
    S = S.replace("01", "")
    S = S.replace("10", "")
    if ((not "01" in S) and (not "10" in S)):
        break
print(len_s - len(S))

### FIXED CODE ###

S = input()
if len(S) == 1:
    print(0)
else:
    print(min(S.count('0'), S.count('1')) * 2)
### BUGGY CODE ###

def main():
    mod = 2**31-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = sum([(i+1)*j for i, j in zip(seq, pow3[:-1])]) % mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = sum([(i+1)*j for i, j in zip(seq, pow3[:-1])]) % mod
        p2 = sum([(2-i)*j for i, j in zip(seq, pow3[:-1])]) % mod
        return p, p2

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m, cnt, pn = max(a+b), n, pow3[n]
    a1, b1, memo = [0]*n, [0]*n, [0]*n

    for k in range(len(bin(m))-2):
        k2 = 2**k
        a1 = [(j & k2) >> k for j in a]
        b1 = [(j & k2) >> k for j in b]
        b_hash, b_hash2 = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        for i, (j, k) in enumerate(zip(memo, A1)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif k == b_hash2:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()

### FIXED CODE ###

def main():
    mod = 2**31-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = 0
        for i, j in enumerate(seq):
            h += (j+1)*pow3[i]
        h %= mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = 0
        p2 = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i]
            p2 += (2-j)*pow3[i]
        return p % mod, p2 % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a1 = [0]*n
    b1 = [0]*n
    memo = [0]*n
    cnt = n
    pn = pow3[n]

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            a1[i] = (j & k2) >> k
        for i, j in enumerate(b):
            b1[i] = (j & k2) >> k
        b_hash, b_hash2 = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        for i, (j, k) in enumerate(zip(memo, A1)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif k == b_hash2:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()
### BUGGY CODE ###

def main():
    N, K, *I = map(int, open(0).read().split())
    A, F = I[:N], I[N:]

    A.sort()
    F.sort(reverse=True)

    ng, ok = -1, 10 ** 12
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if sum(max(0, a - mid // f) for a, f in zip(A, F)) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K, *I = map(int, open(0).read().split())
    A, F = I[:N], I[N:]

    A.sort()
    F.sort(reverse=True)

    ng, ok = -1, 10 ** 12
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if sum(max(0, a - mid // f) for a, f in zip(A, F)) <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


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


S = input()[::-1]


def calculate(rs):
    # rs = reversed(s)

    sss = 0
    dict = [0] * 2019
    dict[0] = 1
    for index, c in enumerate(rs):
        sss = sss + int(c) * 10 ** index
        mod = sss % 2019
        dict[mod] = dict[mod] + 1

    res = 0
    for d in dict:
        if d > 1:
            res = res + d -1

    print(res)


calculate(S)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

K = int(input())
a = 0
for i in range(K):
    a += 7*(10**i)
    a = a % K
    if a == 0:
        print(i+1)
        exit()
print(-1)


### FIXED CODE ###

K = int(input())
a = 0
t = 1
for i in range(K):
    a += 7*t
    a = a % K
    t = t*10
    t = t%K
    if a == 0:
        print(i+1)
        exit()
print(-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
def dfs(v):
    global gone
    stack = [v]
    gone[v] = True
    while stack:
        v = stack.pop()
        for w in graph[v]:
            gone[w] = True
            stack.append(w)

n,m = map(int,input().split())
exist = [False for i in range(n+1)]
gone = [False for i in range(n+1)]
graph = [[] for _ in range(n+1)]
for i in range(m):
    x,y,z = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
    exist[x] = True
    exist[y] = True
ans = 0

for i in range(1,n+1):
    if exist[i] == True:
        if gone[i] == False:
            dfs(i)
            ans += 1
    else:
        ans += 1

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
def dfs(v):
    global gone
    stack = [v]
    gone[v] = True
    while stack:
        v = stack.pop()
        for w in graph[v]:
            if gone[w] == False:
                stack.append(w)
            gone[w] = True

n,m = map(int,input().split())
exist = [False for i in range(n+1)]
gone = [False for i in range(n+1)]
graph = [[] for _ in range(n+1)]
for i in range(m):
    x,y,z = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
    exist[x] = True
    exist[y] = True
ans = 0

for i in range(1,n+1):
    if exist[i] == True:
        if gone[i] == False:
            dfs(i)
            ans += 1
    else:
        ans += 1

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

def solve_145e():
    from collections import namedtuple
    from operator import attrgetter
    import sys
    input = sys.stdin.readline

    Food = namedtuple('Food', 'time_to_eat deliciousness')
    INF = 3000 * 3000 + 1

    N, T = map(int, input().split())
    foods = []
    for _ in range(N):
        row = map(int, input().split())
        foods.append(Food(*row))
    foods.sort(key=attrgetter('time_to_eat'))
    # 同じ料理の組を食べるなら時間のかかるものを後回しにしても結果は悪くならない

    dp = [-INF] * T
    dp[0] = 0
    # dp[time]:=timeに食べ終わる注文の仕方で得られる最大満足度

    ma = 0
    for food in foods:
        # これでフィニッシュの場合
        for time in reversed(range(T)):
            ma = max(ma, dp[time] + food.deliciousness)

        # まだ食べる場合
        for time in reversed(range(T - food.time_to_eat)):
            dp[time + food.time_to_eat] = max(
                dp[time + food.time_to_eat],
                dp[time] + food.deliciousness
            )

    print(ma)
    return


if __name__ == '__main__':
    solve_145e()


### FIXED CODE ###

def solve():
    from collections import namedtuple
    import sys

    input = sys.stdin.readline
    Dish = namedtuple('Dish', 'idx cost pt')

    n, t = map(int, input().split())
    dishes = []
    for idx in range(1, n + 1):
        cost, pt = map(int, input().split())
        dishes.append(Dish(idx=idx, cost=cost, pt=pt))

    dp_ht = [[0] * t for _ in range(n + 2)]  # head->tail
    dp_th = [[0] * t for _ in range(n + 2)]  # tail->head
    # dp[注文可能な範囲の端][完食にかかる総時間]:= 美味しさの最大値

    for dish in dishes:
        for cost_ in range(t):
            if cost_ >= dish.cost:
                dp_ht[dish.idx][cost_] = max(dp_ht[dish.idx - 1][cost_],
                                             dp_ht[dish.idx - 1][cost_ - dish.cost] + dish.pt)
            else:
                dp_ht[dish.idx][cost_] = dp_ht[dish.idx - 1][cost_]

    for dish in reversed(dishes):
        for cost_ in range(t):
            if cost_ >= dish.cost:
                dp_th[dish.idx][cost_] = max(dp_th[dish.idx + 1][cost_],
                                             dp_th[dish.idx + 1][cost_ - dish.cost] + dish.pt)
            else:
                dp_th[dish.idx][cost_] = dp_th[dish.idx + 1][cost_]

    ret = 0
    for last_dish in dishes:
        for cost_ in range(t):
            ret = max(ret, dp_ht[last_dish.idx - 1][cost_] + dp_th[last_dish.idx + 1][t - 1 - cost_] + last_dish.pt)
    return ret


print(solve())
### BUGGY CODE ###

#!/usr/bin/env python

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

ans = 0 
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if s == x + y + z:
                ans += 1

print(ans)


### FIXED CODE ###

#!/usr/bin/env python

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

ans = 0 
for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-(x + y) <= k:
            ans += 1

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

import math

n, m = [int(i) for i in input().split()]


def combi(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


a = [-1]
for mi in range(m):
    a.append(int(input()))
a.append(n+1)

ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += combi(k - i, i) % 1000000007
    ans = ans * cnt % 1000000007

print(ans)


### FIXED CODE ###

n, m = [int(i) for i in input().split()]

b = [0 for i in range(n+1)]

for mi in range(m):
    b[int(input())] = 1
cnt = 0
s = [0 for i in range(n+1)]
s[0] = 1
if b[1] == 0:
    s[1] = 1
else:
    s[1] = 0
for ni in range(2,n+1):
    if b[ni] == 0:
        s[ni] = (s[ni-1] + s[ni-2]) % 1000000007
    else:
        s[ni] = 0
print(s[n])
### BUGGY CODE ###

def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))

    ans = 0
    for ia in range(N):
        for ib in range(ia+1, N-1):
            a = L[ia]
            b = L[ib]

            c_min = max(a-b, b-a)
            c_max = a + b

            for ic in range(ib+1, N):
                c = L[ic]
                if c >= c_max:
                    break
                if c <= c_min:
                    continue
                ans += 1

    print(ans)
main()

### FIXED CODE ###

from bisect import bisect_left, bisect_right

def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))

    ans = 0
    for ia in range(N):
        for ib in range(ia+1, N-1):
            a = L[ia]
            b = L[ib]

            c_min = max(a-b, b-a)
            c_max = a + b
            ic_begin = bisect_right(L, c_min, lo=ib+1)
            ic_end   = bisect_left( L, c_max, lo=ib+1)

            ans += ic_end - ic_begin

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

K, S = tuple(map(int, input().split()))

ret = 0 
for X in range(K+1):
  for Y in range(X, K+1):
    for Z in range(Y, K+1):
      if X + Y + Z == S:
        if X == Y and Y == Z: ret += 1
        elif X != Y and Y != Z and Z != X: ret += 6
        else: ret += 3

print (ret)

### FIXED CODE ###

K, S = tuple(map(int, input().split()))

ret = 0 
for X in range(K+1):
  for Y in range(X, K+1):
    Z = S - X - Y
    if Z < Y: break
    if Z >= 0 and Z <= K:
      if X == Y and Y == Z: ret += 1
      elif X != Y and Y != Z and Z != X: ret += 6
      else: ret += 3

print (ret)
### BUGGY CODE ###

game_num, k = map(int, input().split())
r_score, s_score, p_score = map(int, input().split())
game = input()
score = 0
waste_r, waste_s, waste_p = [], [], []

for i in range(game_num):
    if i < k:
        pass
    elif game[i] == 'r' and game[i - k] == 'r' and not (i - k) in waste_r:
        waste_r.append(i)
    elif game[i] == 's' and game[i - k] == 's' and not (i - k) in waste_s:
        waste_s.append(i)
    elif game[i] == 'p' and game[i - k] == 'p' and not (i - k) in waste_p:
        waste_p.append(i)

r_count, s_count, p_count = map(lambda x: game.count(x), ['r', 's', 'p'])

score += r_count * p_score + s_count * r_score + p_count * s_score
score -= len(waste_r) * p_score + len(waste_s) * r_score + len(waste_p) * s_score
print(score)

### FIXED CODE ###

game_num, k = map(int, input().split())
r_score, s_score, p_score = map(int, input().split())
game = input()
score = 0
waste_r, waste_s, waste_p = [], [], []
count_waste_r = count_waste_s = count_waste_p = 0

for i in range(game_num):
    if i < k:
        pass
    elif game[i] == 'r' and game[i - k] == 'r' and not (i - k) in waste_r:
        count_waste_r += 1
        if len(waste_r) > k:
            waste_r.pop(0)
        waste_r.append(i)
    elif game[i] == 's' and game[i - k] == 's' and not (i - k) in waste_s:
        count_waste_s += 1
        if len(waste_s) > k:
            waste_s.pop(0)
        waste_s.append(i)
    elif game[i] == 'p' and game[i - k] == 'p' and not (i - k) in waste_p:
        count_waste_p += 1
        if len(waste_p) >  k:
            waste_p.pop(0)
        waste_p.append(i)

r_count, s_count, p_count = map(lambda x: game.count(x), ['r', 's', 'p'])

score += r_count * p_score + s_count * r_score + p_count * s_score
score -= count_waste_r * p_score + count_waste_s * r_score + count_waste_p * s_score
print(score)
### BUGGY CODE ###

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

d = {}
def divisor(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1

            rev = n // i
            if i != rev:
                if rev not in d:
                    d[rev] = 1
                else:
                    d[rev] += 1

for num in A:
    divisor(num)

ans = 1
for key, val in d.items():
    if val >= N - 1:
        ans = max(ans, key)

print(ans)

### FIXED CODE ###

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

def ABC125gcd(x, y):
    if min(x, y) == 0:
        return max(x, y)
    else:
        return ABC125gcd(y, x % y)

L = [0] * N
R = [0] * N

for i in range(1, N):
    L[i] = ABC125gcd(L[i - 1], A[i - 1])
    R[N - 1 - i] = ABC125gcd(R[N - i], A[N - i])

ans = 1
for i in range(N):
    ans = max(ans, ABC125gcd(L[i], R[i]))
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())

mode = 1
for i in range(Q):
  query = input()
  if query=='1':
    mode *= -1
  else:
    _, F, C = query.split()
    if F=='1':
      if mode==1:
        S = C+S
      else:
        S = S+C
    else:
      if mode==1:
        S = S+C
      else:
        S = C+S

if mode==-1:
  S = S[::-1]

print(S)


### FIXED CODE ###

S = input()
Q = int(input())

add_to_last = []
add_to_beginning = []

queries = [input() for _ in range(Q)]

mode = 1
for i in range(Q):
  query = queries[i]
  if query=='1':
    mode *= -1
  else:
    _, F, C = query.split()
    if F=='1':
      if mode==1:
        add_to_beginning.append(C)
      else:
        add_to_last.append(C)
    else:
      if mode==1:
        add_to_last.append(C)
      else:
        add_to_beginning.append(C)   

if mode==1:
  add_to_beginning.reverse()
  print("".join(add_to_beginning), end="")
  print(S, end="")
  print("".join(add_to_last))
else:
  add_to_last.reverse()
  print("".join(add_to_last), end="")
  print(S[::-1], end="")
  print("".join(add_to_beginning))
### BUGGY CODE ###

n, k = list(map(int, input().split()))
s = [0] * k
for i in range(k):
     lr = list(map(int, input().split()))
     s[i] = range(lr[0], lr[1]+1)

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[i] = 1
for i in range(n+1):
    if dp[i] == 0:
        continue
    for lr in s:
        for d in lr:
            if i+d <= n:
                dp[i+d] = (dp[i+d] + dp[i]) % mod

print(dp[n] % mod)


### FIXED CODE ###

# DP, 累積和
n, k = list(map(int, input().split()))
s = list()
for i in range(k):
     l, r = list(map(int, input().split()))
     s.append((l, r))

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[1] = 1
dpsum = [0] * (n+1)
dpsum[1] = 1
for i in range(2, n+1):
    for l, r in s:
        li = i-r
        ri = i-l
        if ri < 1: continue
        li = max(li, 1)
        dp[i] = (dp[i] + dpsum[ri] - dpsum[li-1]) % mod
    dpsum[i] = (dpsum[i-1] + dp[i]) % mod
    
print(dp[n])
### BUGGY CODE ###

n, m = map(int, input().split())
ans = 1
for i in range(1, m // n+1):
    if m % i == 0:
        ans = i
print(ans)

### FIXED CODE ###

import math
n, m = map(int, input().split())
ans = 1
k = m
soy = []
for i in range(2, int(math.sqrt(m))+1):
    if k % i == 0:
        are = 0
        while True:
            if k % i == 0:
                k = k // i
                are += 1
            else:
                break
        soy.append([i, are])
if k != 1:
    soy.append([k, 1])
for i in range(10-len(soy)):
    soy.append([1, 0])
for a in range(soy[0][1] + 1):
    for b in range(soy[1][1] + 1):
        for c in range(soy[2][1] + 1):
            for d in range(soy[3][1] + 1):
                for e in range(soy[4][1] + 1):
                    for f in range(soy[5][1] + 1):
                        for g in range(soy[6][1] + 1):
                            for h in range(soy[7][1] + 1):
                                for i in range(soy[8][1] + 1):
                                    for j in range(soy[9][1] + 1):
                                        t = soy[0][0]**a * soy[1][0]**b * soy[2][0]**c * soy[3][0]**d * soy[4][0]**e * soy[5][0]**f * soy[6][0]**g * soy[7][0]**h * soy[8][0]**i * soy[9][0]**j
                                        if n <= t:
                                        	ans = max(ans, m//t)
print(ans)
### BUGGY CODE ###

n=int(input())
mod, ans=7+10**9, 0
mylist=list(map(int, input().split()))
mylist.insert(0,0)
for l in range(1,n):
    for k in range(1,n-l+1):
        ans+=mylist[l]*mylist[l+k]%mod
        ans=ans%mod
print(ans)

### FIXED CODE ###

n=int(input())
mod, ans=7+10**9, 0
a=list(map(int, input().split()))
b=[0]
for l in range(n):
    b.append(b[l]+a[l])
for k in range(n-1):
    s=(b[n]-b[k+1])%mod
    ans+=a[k]*s
    ans%=mod
print(ans)