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

# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

dx = [0,1,0,-1]
dy = [1,0,-1,0]

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

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '#'])

if len(black_deque) == H*W:
    print(0)
    exit(0)

for x,y in black_deque:
    A[x][y] = 0

while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    if x+1 < H and A[x+1][y]=='.':
        black_deque.append((x+1, y))
        A[x+1][y] = depth+1
    if 0 <= x-1 and A[x-1][y]=='.':
        black_deque.append((x-1, y))
        A[x-1][y] = depth+1
    if y+1 < W and A[x][y+1]=='.':
        black_deque.append((x, y+1))
        A[x][y+1] = depth+1
    if 0 <= y-1 and A[x][y-1]=='.':
        black_deque.append((x, y-1))
        A[x][y-1] = depth+1

    tansaku = [(x+dx[k], y+dy[k]) for k in range(4)
        if 0 <= x+dx[k] < H and
           0 <= y+dy[k] < W and
           A[x+dx[k]][y+dy[k]] == '.'
    ]
    for new_x,new_y in tansaku:
        black_deque.append((new_x, new_y))
        A[new_x][new_y] = depth+1

print(depth)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

dx = [0,1,0,-1]
dy = [1,0,-1,0]

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

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '#'])

if len(black_deque) == H*W:
    print(0)
    exit(0)

for x,y in black_deque:
    A[x][y] = 0

while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    for k in range(4):
        new_x = x+dx[k]
        new_y = y+dy[k]
        if 0 <= new_x < H and \
           0 <= new_y < W and \
           A[new_x][new_y] == '.':
            black_deque.append((new_x, new_y))
            A[new_x][new_y] = depth+1

print(depth)
### BUGGY CODE ###

import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os
    import re
    with open(__file__) as f:
        source = f.read().split('###''nbacl')
    for s in source[1:]:
        s = re.sub("'''.*", '', s)
        sp = s.split(maxsplit=1)
        if os.path.dirname(sp[0]):
            os.makedirs(os.path.dirname(sp[0]), exist_ok=True)
        with open(sp[0], 'w') as f:
            f.write(sp[1])

    import nbmodule
    nbmodule.cc.compile()
    exit(0)

from nbmodule import solve
import numpy as np
i8 = np.int64
i4 = np.int32


def main():
    f = open(0)
    N, K = [int(x) for x in f.readline().split()]
    LR = np.fromstring(f.read(), i8, sep=' ').reshape((-1, 2)).T.copy()
    L = LR[0]
    R = LR[1]
    arg = np.argsort(L)
    left = L[arg]
    right = R[arg]
    w = right - left + 1
    ans = solve(N, left, w)
    print(ans)


if __name__ == '__main__':
    main()

'''
###nbacl nbmodule.py
import numpy as np
from numba import njit
from numba.types import i8, i4
from numba.pycc import CC
ni4 = np.int32
ni8 = np.int64
cc = CC('nbmodule')

MOD = 998244353


@cc.export('solve', (i8, i8[:], i8[:]))
def solve(N, left, w):
    l0 = w.max()
    dp_len = N + l0
    dp_prev = np.zeros(dp_len, ni8)
    dp_prev[l0] = 1
    dp = np.zeros(dp_len, ni8)
    left_min = left[0]
    ret = 0
    while l0 + left_min < dp_len:
        for k in range(left.shape[0]):
            pre = 0
            for i in range(l0 + left[k], dp_len):
                cur = pre + dp_prev[i - left[k]] - dp_prev[i - left[k] - w[k]]
                dp[i] += cur
                pre = cur
        ret += dp[-1]
        dp_prev, dp = dp, dp_prev
        dp_prev %= MOD
        dp.fill(0)
        l0 += left_min

    return ret % MOD

if __name__ == '__main__':
    cc.compile()
'''



### FIXED CODE ###

import numpy as np
from numba import njit
from numba.types import i8
ni8 = np.int64
MOD = 998244353


@njit((i8[:,::-1], i8[:], i8, i8), cache=True)
def solve(lr, dp, n, k):
    acc_dp = np.ones_like(dp)
    for i in range(1, n):
        val = 0
        for j in range(k):
            a = i - lr[j, 0]
            if a < 0:
                continue
            b = i - lr[j, 1] - 1
            val += acc_dp[a] - (acc_dp[b] if b >= 0 else 0)
        dp[i] = val % MOD
        acc_dp[i] = (acc_dp[i - 1] + dp[i]) % MOD
    return dp[n - 1]


def main():
    f = open(0)
    n, k = [int(x) for x in f.readline().split()]
    lr = np.fromstring(f.read(), ni8, sep=' ').reshape((-1, 2))
    dp = np.zeros(n, ni8)
    dp[0] = 1
    ans = solve(lr, dp, n, k)
    print(ans)

main()
### BUGGY CODE ###

S = list(input())
i = 0
ans = 0
if len(S)==1:
    print(0)
    exit()
while (1):
    #print(ans, S, i)
    if (S[i]=="0" and S[i+1]=="1") or (S[i]=="1" and S[i+1]=="0"):
        del S[i:i+2]
        ans += 2
        i = 0
        if len(S)<=1:
            break
        continue
    if i>=len(S)-2:
        break
    else:
        i += 1
print(ans)

### FIXED CODE ###

S = list(input())
cnt0 = cnt1 = 0
for i in S:
    if i == "0":
        cnt0 += 1
    if i == "1":
        cnt1 += 1
print(min(cnt1, cnt0)*2)
### BUGGY CODE ###

def larger(x, y):
	if x > y:
		return x
	return y

H, W = map(int, input().split())
field = []
for i in range(0, H):
	field.append(input())
upper = []
down = []
left = []
right = []
for i in range(0, H):
	lst1 = []
	lst2 = []
	lst3 = []
	lst4 = []
	for j in range(0, W):
		lst1.append(0)
		lst2.append(0)
		lst3.append(0)
		lst4.append(0)
	upper.append(lst1)
	down.append(lst2)
	left.append(lst3)
	right.append(lst4)
for i in range(0, H):
	for j in range(0, W):
		if field[i][j] == '.':
			
			for k in range(1, H):
				if i - k < 0:
					break
				if field[i-k][j] == '#':
					break
				upper[i][j] += 1
			for k in range(1, H):
				if i + k >= H:
					break
				if field[i+k][j] == '#':
					break
				down[i][j] += 1
			for k in range(1, W):
				if j - k < 0:
					break
				if field[i][j-k] == '#':
					break
				left[i][j] += 1
			for k in range(1, W):
				if j + k >= W:
					break
				if field[i][j+k] == '#':
					break
				right[i][j] += 1
max = 0
for i in range(0, H):
	for j in range(0, W):
		if field[i][j] == '.':
			lamp = upper[i][j] + down[i][j] + left[i][j] + right[i][j] + 1
			max = larger(max, lamp)
print(max)

### FIXED CODE ###

def larger(x, y):
	if x > y:
		return x
	return y

H, W = map(int, input().split())
field = []
for i in range(0, H):
	field.append(input())
upper = []
down = []
left = []
right = []
for i in range(0, H):
	lst1 = []
	lst2 = []
	lst3 = []
	lst4 = []
	for j in range(0, W):
		lst1.append(0)
		lst2.append(0)
		lst3.append(0)
		lst4.append(0)
	upper.append(lst1)
	down.append(lst2)
	left.append(lst3)
	right.append(lst4)
for i in range(0, H):
	cnt1 = 0
	cnt2 = 0
	for j in range(0, W):
		if field[i][j] == '#':
			cnt1 = 0
		else:
			left[i][j] = cnt1
			cnt1 += 1
		if field[i][-1-j] == '#':
			cnt2 = 0;
		else:
			right[i][-1-j] = cnt2
			cnt2 += 1
for i in range(0, W):
	cnt1 = 0
	cnt2 = 0
	for j in range(0, H):
		if field[j][i] == '#':
			cnt1 = 0
		else:
			upper[j][i] = cnt1
			cnt1 += 1
		if field[-1-j][i] == '#':
			cnt2 = 0
		else:
			down[-1-j][i] = cnt2
			cnt2 += 1
max = 0
for i in range(0, H):
	for j in range(0, W):
		if field[i][j] == '.':
			lamp = upper[i][j] + down[i][j] + left[i][j] + right[i][j] + 1
			max = larger(max, lamp)
print(max)
### BUGGY CODE ###

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

ans = 10**15 
for i in range(K):
    if X>=0:
        X-=D
        if abs(X) < abs(ans):
            ans = abs(X)
    else:
        X+=D
        if abs(X) < abs(ans):
            ans = abs(X)
print(ans)



### FIXED CODE ###

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

X = abs(X)

# Dだけ原点に向かって移動したとき，最も原点に近い座標
r = X%D
# rまでに要した移動回数
q = X//D

# rに到達後は残りの移動回数が偶数か奇数かで場合分け
# K回を超えている場合
if K <= q:
    print(X-D*K)
else:
    # 残り移動可能回数
    rem = K - q

    # 残り移動可能回数が偶数なら，その場所にとどまることできる
    if rem%2 == 0:
        print(r)
    # 奇数なら，絶対に負の側でゴールすることになる．よってr-Dの絶対値であるD-rが解
    else:
        print(D-r)
### BUGGY CODE ###

b = list(map(int, input()))
cnt = 0
while len(b) > 1:

    if len(list(set(b))) == 1:
        break
    if b[0] != b[1]:
        b = b[2:]
        cnt += 1
        continue
    temp = b[:1]
    b = b[1:]
    b.append(*temp)
print(cnt * 2)


### FIXED CODE ###

s = input()
zom = min(s.count("1"),s.count("0"))
if len(set(list(s))) == 1:
    zom = 0
print(zom*2)
### BUGGY CODE ###

n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
r = 1
d *= 2
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    m[i].append(r - 1)
    m[i][1] = (m[i][1] + a - 1) // a
res = 0
for i in range(n):
    if m[i][1] > 0:
        res += m[i][1]
        for j in range(i + 1, m[i][2] + 1):
            m[j][1] -= m[i][1]
print(res)


### FIXED CODE ###

from collections import deque
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
r = 1
d *= 2
q=deque([])
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    m[i].append(r)
    m[i][1] = (m[i][1] + a - 1) // a
res = 0
tdamage = 0
for i in range(n):
    while q and q[0][0] <= i:
        minus = q.popleft()
        tdamage -= minus[1]
    m[i][1] -= tdamage
    if m[i][1] > 0:
        res += m[i][1]
        tdamage += m[i][1]
        q.append([m[i][2],m[i][1]])
print(res)
### BUGGY CODE ###

import numpy as np
def s():
    return raw_input()
def li():
    return map(int,raw_input().split())

st = []
X = list(s())

st.append(X[0])
X.pop(0)
#for i in range(len(X)-2):
while len(X) > 0:
    st.append(X[0])
    X.pop(0)
    if st[-1] == 'T' and st[-2] == 'S':
        st.pop()
        st.pop()
print len(st)



### FIXED CODE ###

import numpy as np
def s():
    return raw_input()
def li():
    return map(int,raw_input().split())

st = []
X = list(s())
N = len(X)
X.reverse()
st.append(X[-1])
X.pop()
#for i in range(len(X)-2):
for i in range(N-1):
    st.append(X[-1])
    X.pop()
    if len(st) >= 2:
        if st[-1] == 'T' and st[-2] == 'S':
            st.pop()
            st.pop()
print len(st)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    from fractions import gcd

    def lcd(x, y):
        g = gcd(x, y)
        return x * y // g

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

    a.sort(reverse=True)
    l = 1
    for e in a:
        l = lcd(l, e)

    ans = 0
    for e in a:
        ans += (l // e) % mod
        ans %= mod

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from fractions import gcd


def lcm(a, b):
    return a * b // gcd(a, b)


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

l = 1
for e in a:
    l = lcm(l, e)

l %= mod

ans = 0
for e in a:
    ans += l * pow(e, mod - 2, mod)
    ans %= mod

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

n = int(input())
s = input()
sub=0
flg_r = 0
flg_g = 0
flg_b = 0#0だと見つかってない
for a in range(n-2):
    rgb = ("R","G","B")
    #print(a)
    for b in range(a+1,n-1):
        #print(a,b)
        rgb_kake = list(rgb)
        rgb_kake.remove(s[a])
        if s[a] != s[b]:
            #print(s[a],s[b],rgb, rgb_kake)
            rgb_kake.remove(s[b])
            for c in range(b+1,n):
                if s[c] == rgb_kake[0]:
                    #print(a,b,c)
                    if b-a != c-b:
                        sub+=1
print(sub)


### FIXED CODE ###

n = int(input())
s = input()
r_cnt = s.count("R")
g_cnt = s.count("G")
b_cnt = s.count("B")

sub = r_cnt * g_cnt * b_cnt

for i in range(n):
    for d in range(n):
        j = i+d
        k = j+d
        if k >= n:
            break

        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            sub-=1
print(sub)
### BUGGY CODE ###

import fractions
from functools import reduce

import copy

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

ans = 1

for i in range(n):
  m = copy.copy(l)
  m.pop(i)
  gcd = gcd_list(m)
  if gcd > ans:
    ans = gcd

print(ans)
  

### FIXED CODE ###

import fractions

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

gcd_l = [0]
gcd_r = [0]

for i in range(n):
  gcd_l.append(fractions.gcd(gcd_l[i], l[i]))
  gcd_r.append(fractions.gcd(gcd_r[i], l[-(i+1)]))
gcd_r = gcd_r[::-1]
# print(gcd_l)
# print(gcd_r)

ans = [0]*n
for i in range(n):
  ans[i] = fractions.gcd(gcd_l[i], gcd_r[i+1])
print(max(ans))
### BUGGY CODE ###

N = int(input())
a=list(map(int,input().split()))
gos=[]
for i in range(1,N):
    mae=sum(a[:i])
    ato=sum(a)-mae
    gos.append((abs(mae-ato)))
print(min(gos))

### FIXED CODE ###

N = int(input())
a=list(map(int,input().split()))
ans=2020202020
s=sum(a)
mae=a[0]
for i in range(1,N):
    mae+=a[i]
    ato=s-mae
    if mae-ato>0:
        ans=min(abs(sum(a[:i])-sum(a[i:])),abs(sum(a[:i+1])-sum(a[i+1:])))
        break
    else:
        ans=min(ans,abs(mae-ato))
print(ans)
### BUGGY CODE ###

import copy
N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))

x=max(A)
for i in range(N):
    if A[i]==x:
        B=copy.copy(A)
        B.pop(i)
        print(max(B))
    else:
        print(x)

### FIXED CODE ###

import copy
N=int(input())
A=[]
for i in range(N):
  A.append(int(input()))

x=max(A)
count=(A.count(x))
index=[]
if count!=1:
    for i in range(N):
        print(x)
else:
    B=copy.copy(A)
    B.remove(x)
    y=max(B)
    for i in range(N):
        if A[i]==x:
            print(y)
        else:
            print(x)
### BUGGY CODE ###

x,y,a=map(int,input().split())
s=0
for i in range(x,y+1):
    if i%a==0:
        s+=1
print(s)

### FIXED CODE ###

a,b,x=map(int,input().split())
print(b//x-(a-1)//x)
#コピペです。
### BUGGY CODE ###

import heapq

class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

sorted_A = []
A_q = Heapq(A, True)
for i in range(X):
    sorted_A.append(A_q.pop())
sorted_B = []
B_q = Heapq(B, True)
for i in range(Y):
    sorted_B.append(B_q.pop())
sorted_C = []
C_q = Heapq(C, True)
for i in range(Z):
    sorted_C.append(C_q.pop())
# pop_c_list = []
# pop_b_list = []
#
# max_list = []
# for i in range(min(X, K)):
#     a = A_q.pop()
#     for j in range(min(Y, K)):
#         b = B_q.pop()
#         pop_b_list.append(b)
#         for k in range(min(Z, K)):
#             c = C_q.pop()
#             pop_c_list.append(c)
#             max_list.append(a+b+c)
#         for pop_c in pop_c_list:
#             C_q.push(pop_c)
#     for pop_b in pop_b_list:
#         B_q.push(pop_b)

# A.sort(reverse=True)
# B.sort(reverse=True)
# C.sort(reverse=True)

max_list = []
for a in sorted_A[:K]:
    for b in sorted_B[:K]:
        for c in sorted_C[:K]:
            max_list.append(a + b + c)

max_list_q = Heapq(max_list, True)
for i in range(K):
    print(max_list_q.pop())

### FIXED CODE ###

import heapq

import itertools

class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
C.sort(reverse=True)

p = itertools.product(A, B)
A_B_list = [sum(v) for v in itertools.product(A, B)]
A_B_list.sort(reverse=True)
A_B_C_list = [sum(v) for v in itertools.product(A_B_list[:3000], C[:3000])]
A_B_C_list.sort(reverse=True)

for ans in A_B_C_list[:K]:
    print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9 + 7
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        ans += A[i] ^ A[j]
ans = ans % MOD
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))

MOD = 10**9 + 7
ans = 0

for i in range(60):
    a = (A >> i) & 1
    count0 = np.count_nonzero(a)
    count1 = N - count0
    tmp = 2**i
    n = count0 * count1
    tmp = tmp * n
    ans += tmp
    ans = ans % MOD
print(ans)
### BUGGY CODE ###

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

S = input().rstrip()
Q = int(input())
Query = []

flag = 0

for _ in range(Q):
    Query.append(input().rstrip().split())

for i in Query:
    if i[0] == "1":
        flag += 1
    elif i[1] == "1":
        if flag % 2 == 0:
            S = i[2] + S
        else:
            S += i[2]
    else:
        if flag % 2 == 0:
            S += i[2]
        else:
            S = i[2] + S
if flag % 2 == 0:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

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

S = deque(list(input().rstrip()))
Q = int(input())
Query = []

flag = 0

for _ in range(Q):
    Query.append(input().rstrip().split())

for i in Query:
    if i[0] == "1":
        flag += 1
    elif i[1] == "1":
        if flag % 2 == 0:
            S.appendleft(i[2])
        else:
            S.append(i[2])
    else:
        if flag % 2 == 0:
            S.append(i[2])
        else:
            S.appendleft(i[2])
if flag % 2 == 0:
    print("".join(list(S)))
else:
    print("".join(list(S))[::-1])
### BUGGY CODE ###

import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

data1 = getInputListInt()
n = data1[0]
q = data1[1]

data2 = getSomeInputListInt(n-1)

data3 = getSomeInputListInt(q)

ans = np.zeros(n)

for i in range(len(data3)):
    ans[data3[i][0]-1] += data3[i][1]

treeList = [[] for _ in range(n)]

for i in range(len(data2)):
    treeList[data2[i][0]-1].append(data2[i][1]-1)
    treeList[data2[i][1]-1].append(data2[i][0]-1)

def treeTrace(crnt, prnt):
    for i in range(len(treeList[crnt])):
        if prnt == treeList[crnt][i]:
            continue
        ans[treeList[crnt][i]] += ans[crnt]

        treeTrace(treeList[crnt][i], crnt)

treeTrace(0, -1)

for s in ans:
    print(int(s), end =" ")


### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)
ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)
### BUGGY CODE ###

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

def sol():
    S = input()
    T = input()

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

    for i, s in enumerate(S):
        posS[s].append(i)

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000*10000)

INF = float("inf") #const

def main():
    n,m = map(int,input().split())
    a = [int(input()) for i in range(m)]
    dp = [0]*(n+1)
    dp[0],dp[1] = 1,1

    for i in range(2,n+1):
        if issafe(i-1,a):
            dp[i] += dp[i-1]
        if issafe(i-2,a):
            dp[i] += dp[i-2]

    print(dp[n]%(10**9+7))


def issafe(i,a):
    if i in a:
        return False
    else:
        return True


if __name__ == "__main__":
    main()


### FIXED CODE ###

INF = float("inf") #const

def main():
    n,m = map(int,input().split())
    issafe = [True]*n
    for i in range(m):
        a = int(input())
        issafe[a] = False
    dp = [0]*(n+1)
    dp[0],dp[1] = 1,1

    for i in range(2,n+1):
        if issafe[i-1]:
            dp[i] += dp[i-1]
        if issafe[i-2]:
            dp[i] += dp[i-2]

    print(dp[n]%(10**9+7))


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

if __name__ == '__main__':
    MODULO = 10**9 + 7
    n = int(input())
    A = list(map(int, input().split()))
    total = 0
    for i in range(n):
        for j in range(i+1, n):
            total = (total + A[i] * A[j]) % MODULO
    print(total)


### FIXED CODE ###

if __name__ == '__main__':
    MODULO = 10**9 + 7
    n = int(input())
    A = list(map(int, input().split()))
    total = 0
    sq = 0
    for i in range(n):
        total = (total + A[i]) #% MODULO
        sq = (pow(A[i], 2) + sq) #% MODULO
    total = ((pow(total, 2) - sq) // 2) % MODULO
    print(total )
### BUGGY CODE ###

INF = 10**9
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    keys.append((a, c))

dp = [INF]*(2**n)
dp[0] = 0
for a, c in keys:
    tmp = [INF]*(2**n)
    for j in range(2**n):
        if dp[j] == INF:
            continue
        tmp[j] = min(tmp[j], dp[j])
        tmp[j|c] = min(tmp[j|c], dp[j]+a)
    dp = tmp

print(dp[-1] if dp[-1]<INF else -1)


### FIXED CODE ###

INF = 10**9
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    keys.append((a, c))

dp = [INF]*(2**n)
dp[0] = 0
for a, c in keys:
    tmp = [INF]*(2**n)
    for j, d in enumerate(dp):
        if d == INF:
            continue
        if d < tmp[j]:
            tmp[j] = d
        if d+a < tmp[j|c]:
            tmp[j|c] = d+a
    dp = tmp

print(dp[-1] if dp[-1]<INF else -1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(len(a)-1):
    for j in range(i+1, len(a)):
        x += (a[i]*a[j])%(10**9+7)
print(x%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
m = sum(a)
for i in range(len(a)-1):
    m = (m-a[i])%(10**9+7)
    x += a[i]*m
    x = x%(10**9+7)
print(x%(10**9+7))