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

N,M = map(int,input().split())
from collections import defaultdict
AB = [[0,0]]*N
for n in range(N):
    temp = list(map(int,input().split()))
    if temp[0] <= M:
        AB[n] = temp
work_schedule = [0]*M
sorted_AB = sorted(AB,key=lambda x:(-x[1],x[0]))
hist = defaultdict(int)
for work in sorted_AB:
    hist[work[0]] = work[0]-1
    while True:
        if hist[work[0]] >= M:
            break
        elif work_schedule[hist[work[0]]] == 0:
            work_schedule[hist[work[0]]]  = work[1]
            break
        elif  work_schedule[hist[work[0]]] != 0:
            hist[work[0]] += 1
print(sum(work_schedule))

### FIXED CODE ###

from collections import defaultdict
import heapq

n, m = map(int, input().split())
dct = defaultdict(list)

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

h = []
res = 0

for i in range(1, m + 1):
    if dct[i]:
        for item in dct[i]:
            heapq.heappush(h, item)
    if h:
        res += heapq.heappop(h)

print(-res)
### BUGGY CODE ###

n=int(input());
A=[int(input().replace(' ',''),2)for _ in[0]*n]
p=[0]*2**n
p[0]=1
for I in range(2**n-1):
 a=A[bin(I).count('1')]&~I
 for j in range(n):
  if a&2**j:p[I+2**j]+=p[I];p[I+2**j]%=10**9+7
print(p[-1])

### FIXED CODE ###

n=int(input());
A=[int(input().replace(' ',''),2)for _ in[0]*n]
dp=[0]*2**n
dp[0]=1
for I in range(2**n-1):
    a=A[bin(I).count('1')]&~I
    for j in range(n):
        if a&1<<j:dp[I|1<<j]=(dp[I|1<<j]+dp[I])%(10**9+7)
print(dp[-1])
### BUGGY CODE ###

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

passcard = [i+l[0][0] for i in range(l[0][1] - l[0][0]+1)]
for t in range(n[1]-1):
    passcard = [i for i in passcard if l[t+1][0] <= i <= l[t+1][1]]
    
print(len(passcard))

### FIXED CODE ###

n = list(map(int,input().split()))
l = [list(map(int,input().split())) for i in range(n[1])]
minp = l[0][0]
maxp = l[0][1]
for t in range(n[1]):
    minp = max(minp,l[t][0])
    maxp = min(maxp,l[t][1])
print(max(0,maxp-minp+1))
### BUGGY CODE ###

n = int(input())

ss = []
for i in range(n):
    tmp = list(input())
    tmp.sort()
    ss.append(tmp)

matrix = [[0 for _ in range(n)] for _ in range(n)]
checked = set()

for i in range(n-1):
    if i in checked:
        continue
    same_str = set()
    for j in range(i+1, n):
        if ss[i] == ss[j]:
            matrix[i][j] = 1

            for s in same_str:
                matrix[s][j] = 1

            same_str.add(j)
            checked.add(j)

count = 0
for row in matrix:
    count += sum(row)

print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())

#ss = [sorted(list(input())) for _ in range(n)]
ss = []
checked = {}
count = 0
for i in range(n):
    tmp = list(input())
    tmp.sort()
    tmp = str(tmp)
    if not(tmp in checked):
        checked[tmp] = 1
    else:
        count += checked[tmp]
        checked[tmp] += 1

print(count)
### BUGGY CODE ###

N = int(input())
ans=0

for i in range(N):
  ans+=i
  
print(ans)

### FIXED CODE ###

N = int(input())
ans=(N*(N-1))//2
  
print(int(ans))
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

li = [r, g, b]
li.sort(reverse=True)

num_max_0 = n//li[0]
num_max_1 = n//li[1]
ans = 0
for num_0 in range(num_max_0 + 1):
    for num_1 in range(num_max_1 + 1):
        ball_01 = num_0*li[0] + num_1*li[1]
        ball_2 = n - ball_01

        if ball_2 >= 0 and ball_2 % li[2] == 0:
            ans += 1
print(ans)

### FIXED CODE ###

r, g, b, n = map(int, input().split())

num_max_r = n//r

ans = 0
for num_r in range(num_max_r + 1):
    
    n_r = n - num_r*r
    num_max_g = n_r//g
    
    for num_g in range(num_max_g + 1):
        n_r_g = n_r - num_g*g
        
        if n_r_g >= 0 and n_r_g % b == 0:
            ans += 1

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



N, M = [int(x) for x in input().split()]
a = list(int(input()) for _ in range(M))

MOD = 10 ** 9 + 7
dp = [0] * (N + 1)
dp[0] = 1

for i in range(1, N + 1):
  if i in a:
    continue
  x = dp[i - 1]
  if i > 1:
    x += dp[i - 2]
  dp[i] = x % MOD

ans = dp[N]
print(ans)

### FIXED CODE ###



N, M = [int(x) for x in input().split()]
a = set(int(input()) for _ in range(M))

MOD = 10 ** 9 + 7
dp = [0] * (N + 1)
dp[0] = 1

for i in range(1, N + 1):
  if i in a:
    continue
  x = dp[i - 1]
  if i > 1:
    x += dp[i - 2]
  dp[i] = x % MOD

ans = dp[N]
print(ans)
### BUGGY CODE ###

n=int(input())
A=sorted(list(map(int,input().split())),reverse=True)
m=0
i=0
while i<len(A):
    if A[i:].count(A[i])>=2:
        if m==0:
            m=A[i]
            i+=2
        else:
            n=A[i]
            print(m*n)
            exit()
    else:
        i+=1
print(0)

### FIXED CODE ###

from collections import Counter
n=int(input())
A=list(map(int,input().split()))
C=sorted(Counter(A).items(),key=lambda x:x[0],reverse=True)
m=len(C)
for i in range(m):
    if C[i][1]>=4:
        print(C[i][0]**2)
        exit()
    elif C[i][1]>=2:
        a=C[i][0]
        for j in range(i+1,m):
            if C[j][1]>=2:
                print(a*C[j][0])
                exit()
print(0)
### BUGGY CODE ###

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

l = n - k + 1
lis = [0]*l
c = 0
m = 1

for i in range(l):
  for j in range(c, c + k):
    m = m * a[j]
  lis[i] = m
  m = 1
  c += 1
for i in range(n - k):
  if lis[i] < lis[i + 1]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

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

#0, 1
for i in range(n - k):
  if a[i] < a[i + k]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

# テスト
N = int(input())
#print("約数 =", divisors(N))
#print("素因数分解 = ", primeFactor(N)) 

ans = 0
for i in range(1,N+1):
    A = primeFactor(i).values()
    chk = 1
    for a in A:
        chk *= (a+1)
    ans += chk*i

print(ans)

### FIXED CODE ###

#Osa_k法（前処理をした後、素因数分解をO(logN)でできる）

N = int(input())
sieve = [-1] * (N+1)
#prime = []
for i in range(2, N+1):#前処理（各indexについて、割れる最小の素数）
    if sieve[i] == -1:#未探索のとき
        sieve[i] = i
        #prime.append(i)#素数列挙したいとき
        for j in range(i*i, N+1, i):
            if sieve[j] == -1:
                sieve[j] = i
#print(sieve)
#print(prime)

Ans = [1] * (N+1)
for i in range(2, N+1):
    p = sieve[i]
    cur = i
    cnt = 0
    while cur > 1:
        if cur % p == 0:
            cur //= p
            cnt += 1
        else:
            break
    if i == pow(p,cnt):#iの素因数がpのみ
        Ans[i] = i*(cnt+1)
    else:
        Ans[i] = Ans[i//(p**cnt)] * Ans[p**cnt]#それ以外の時、掛算すればOK
#print(Ans)
print(sum(Ans)-1)
### BUGGY CODE ###

def ncr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result *= numerator[k]
    return int(result)
  
n, a, b = map(int, input().split())
whole_sum = (2 ** n) - 1
mod = 10 ** 9 + 7

whole_sum -= ncr(n, a)
whole_sum -= ncr(n, b)

print(whole_sum % mod)

### FIXED CODE ###

#D 復習
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
whole_sum = pow(2, n, mod) - 1

def combinations_mod(n, k, mod):
    X, Y = 1, 1
    for i in range(1, k+1):
        X = (X * (n-i+1))%mod
    for j in range(1, k+1):
        Y = (Y*j)%mod
    result = X * (pow(Y, mod-2, mod))
    return result%mod

whole_sum -= combinations_mod(n, a, mod)
whole_sum -= combinations_mod(n, b, mod)

print(whole_sum % mod)
### BUGGY CODE ###

a, b = map(int, input().split())
for i in range(a, b):
    b = b ^ i
print(b)

### FIXED CODE ###

a, b = map(int, input().split())
if b%2 == 1:
    F0_b = (b+1) // 2 % 2
else:
    F0_b = (b) // 2 % 2 ^ b
c = a - 1
if (c)%2 == 1:
    F0_c = (c+1) // 2 % 2
else:
    F0_c = (c) // 2 % 2 ^ c

print(F0_b ^ F0_c)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s=0
for i in range(0,n-1):
    f=True
    #if a[i]!=0:
    for j in range(i+1,n):
            #if a[j]!=0:
            if j-i==a[j]+a[i]:
                s+=1
                f=False
            if f==True:continue
print(s)

### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
import collections
D=collections.defaultdict(int)
ans=0
for i in range(n):
  D[A[i]+i]+=1
for i in range(n):
  ans+=D[i-A[i]]
print(ans)
### BUGGY CODE ###

import itertools
import sys

readline = sys.stdin.buffer.readline


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return -self.par[self.find(x)]


def main():
    N, M, K = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(M)]
    CD = [list(map(int, readline().split())) for _ in range(K)]

    E = UnionFind(N)

    ans = [0 for _ in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        E.unite(a, b)
        ans[a] -= 1
        ans[b] -= 1

    for i, j in itertools.combinations(list(range(N)), 2):
        if E.same(i, j):
            ans[i] += 1
            ans[j] += 1

    for i, j in CD:
        i -= 1
        j -= 1
        if E.same(i, j):
            ans[i] -= 1
            ans[j] -= 1

    print(*ans)


main()


### FIXED CODE ###

import collections
import itertools
import sys

readline = sys.stdin.buffer.readline


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    N, M, K = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(M)]
    CD = [list(map(int, readline().split())) for _ in range(K)]

    E = UnionFind(N)

    ans = [0 for _ in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        E.unite(a, b)
        ans[a] -= 1
        ans[b] -= 1

    for i in range(N):
        E.find(i)

    ll = collections.defaultdict(int)
    for i in E.par:
        ll[i] += 1

    for i in range(N):
        ans[i] += ll[E.par[i]] - 1

    for i, j in CD:
        i -= 1
        j -= 1
        if E.same(i, j):
            ans[i] -= 1
            ans[j] -= 1

    print(*ans)


main()
### BUGGY CODE ###

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

while abs(N-K) <= N:
  N=abs(N-K)
else:
  print(N)

### FIXED CODE ###

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

t=N%K
ans=min(t,K-t)
print(ans)
### BUGGY CODE ###

import bisect
N,Q = map(int, input().split())
L = [0]*Q
L1 = []
L2 = []
for i in range(Q):
    a,b = map(int, input().split())
    L[i] = (a, b)
    if a == 1:
        L1.append(b)
    else:
        L2.append(b)

L1.sort()
L2.sort()

ans = (N-2)**2
up = N
left = N
for l in L:
    a = l[0]
    b = l[1]
    if a == 1:
        if b > left:
            continue
        idx = bisect.bisect_left(L1, b)
        ans -= (len(L1)-idx)*(up-2)
        L1 = L1[:idx]
        left = b
    else:
        if b > up:
            continue
        idx = bisect.bisect_left(L2, b)
        ans -= (len(L2)-idx)*(left-2)
        L2 = L2[:idx]
        up = b
print(ans)

### FIXED CODE ###

import bisect
N,Q = map(int, input().split())
L = [0]*Q
L1 = []
L2 = []
for i in range(Q):
    a,b = map(int, input().split())
    L[i] = (a, b)
    if a == 1:
        L1.append(b)
    else:
        L2.append(b)

L1.sort()
L2.sort()
M1 = len(L1)
M2 = len(L2)
ans = (N-2)**2
up = N
left = N
for l in L:
    a = l[0]
    b = l[1]
    if a == 1:
        if b > left:
            continue
        idx = bisect.bisect_left(L1, b)
        ans -= (M1-idx)*(up-2)
        M1 = idx
        left = b
    else:
        if b > up:
            continue
        idx = bisect.bisect_left(L2, b)
        ans -= (M2-idx)*(left-2)
        M2 = idx
        up = b
print(ans)
### BUGGY CODE ###

N=int(input())
L=list(map(int, input().split()))
L.sort()
cnt=0

for i in range(0,N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if L[i]<L[j]+L[k]:
        if L[j]<L[i]+L[k]:
          if L[k]<L[i]+L[j]:
            cnt+=1

print(cnt)

### FIXED CODE ###

import bisect

N=int(input())
L=list(map(int, input().split()))
L.sort()

ans=0
for i in range(N-2):
  for j in range(i+1,N-1):
    #small = bisect.bisect_left(L, L[j]-L[i])
    large = bisect.bisect_left(L, L[j]+L[i])    
    #print(i,j,L[i],L[j],"  ",L[j]-L[i],L[j]+L[i],small,large)
    ans += max(large-j-1,0)    

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

import sys
input = sys.stdin.readline

class Factorization:	
	def __init__(self):
		# privateなインスタンス変数を作成
		self.__factors = dict()
		self.__n = 0
	
	
	def get_factors(self, n):
		# [summary] 素因数分解した結果を、辞書([素因数, 指数]...)で返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			# 2より小さい数の場合、素因数分解できない
			return { n:1 }
		else:
			self.__factorization()
			
			return self.__factors
	
	
	def get_divisors(self, n):
		# [summary] 約数をリストに列挙
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return [1]
		else:
			self.__factorization()
			divisors = [1]
			
			for k, v in self.__factors.items():
				import copy
				copy_ = copy.deepcopy(divisors)
								
				for i in range(1, v + 1):
					for c in copy_:
						divisors.append(c * (k ** i))
			
			return divisors

				
	def count_divisors(self, n):
		# [summary] 約数の個数を返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return 1
		else:
			self.__factorization()
			count = 1
			
			for v in self.__factors.values():
				count *= v + 1
			
			return count
	

	def	__factorization(self):
		# [summary]素因数分解した結果を、インスタンス変数に格納
		
		# 2,3,5で、割れなくなるまで割り続ける
		# (末尾に2,3,5のつく数は素数でないことが明白なので
		# 後続の処理で素数のリストに入れないように、先に処理する)
		self.__divide_with(2)
		self.__divide_with(3)
		self.__divide_with(5)
			
		# 平方根以下の素数で総当たりで試し割りする
		# (実際は、素数らしき数)
		import math
		sqrt_ = math.floor(math.sqrt(self.__n))
			
		primes = [7, 11, 13, 17, 19, 23, 29, 31]
		i = 0
		is_break = False
			
		while self.__n > 1:
			for p in primes:
				if p + i <= sqrt_:
					self.__divide_with(p + i)
				else:
					# 試し割りする数が平方根を超えたら、ループを抜ける
					is_break = True
						
					# 1が素因数に追加されることを防止
					if self.__n > 1:
						self.__factors.setdefault(self.__n, 1)
				
			if is_break:
				break
			else:
				i += 30
	
	
	def __divide_with(self, d):
		count = 0
		
		while self.__n % d == 0:
			self.__n //= d
			count += 1
		
		if count > 0:
			self.__factors.setdefault(d, count)


# D - Sum of Divisors
n = int(input())
lib = Factorization()
ans = 0

for i in range(1, n + 1):
	count = lib.count_divisors(i)
	ans += i * count

print(ans)

### FIXED CODE ###

# D - Sum of Divisors
N = int(input())
ans = (1 + N) * N

for i in range(2, N//2 + 1):
	j = 2
	
	while True:
		if i * j <= N:
			
			ans += i * j
			j += 1
		else:
			break

print(ans - 1)
### BUGGY CODE ###

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

visited = {}

for d in lst:
  if d in visited.keys():
    visited[d] += 1
  else:
    visited[d] = 1
for i in range(n):
  visited[lst[i]] -= 1
  ans = 0
  for d in visited.keys():
    v = visited[d]
    ans += v*(v-1)/2
  print(int(ans))
  visited[lst[i]] += 1

### FIXED CODE ###

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

visited = {}

for d in lst:
  if d in visited.keys():
    visited[d] += 1
  else:
    visited[d] = 1
count = 0
for d in visited.keys():
  count += int(visited[d]*(visited[d]-1)/2)
for d in lst:
  v = visited[d] - 1
  ans = count - v
  print(ans)
### BUGGY CODE ###

N, M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())), reverse=True)
B = []

B.append(A.pop(0)//2)
for i in range(1,M):
    if A == []:
        B[0] = B[0]//2
        B = sorted(B, reverse=True)
    else:
        if A[0] > B[0]:
            B.append(A.pop(0)//2)
        else:
            B[0] = B[0]//2
            B = sorted(B, reverse=True)

print(sum(A)+sum(B))

### FIXED CODE ###

N, M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())), reverse=True)
b = []

b.append(A.pop(0)//2)
for i in range(1,M):
    if A == []:
        b.append(b.pop(0)//2)
    else:
        if A[0] > b[0]:
            b.append(A.pop(0)//2)
        else:
            b.append(b.pop(0)//2)

print(sum(A)+sum(b))
### BUGGY CODE ###

k,s=map(int,input().split())
count=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if s==x+y+z:
                count+=1
print(count)

### FIXED CODE ###

k,s=map(int,input().split())
count=0
for x in range(k+1):
    for y in range(k+1):
        if k>=s-(y+x)>=0:
            count+=1
print(count)
### BUGGY CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 5)


def solve(n, m, links):
    if m % 2 == 1:
        print(-1)
        return

    going = [set() for _ in range(n)]
    tree = [set() for _ in range(n)]
    parents = [-1] * n
    q = deque([0])
    while q:
        v = q.popleft()
        for u in links[v]:
            if v in going[u]:
                continue
            going[v].add(u)
            if parents[u] == -1:
                tree[v].add(u)
                parents[u] = v
            q.append(u)

    parities = [len(l) % 2 for l in going]

    # print(going)
    # print(tree)
    # print(parents)
    # print(parities)

    def dfs(v):
        b = parities[v]
        for u in tree[v]:
            c = dfs(u)
            b ^= c
        if b:
            p = parents[v]
            going[p].remove(v)
            going[v].add(p)
        return b

    dfs(0)

    ans = ['{} {}'.format(v + 1, u + 1) for v in range(n) for u in going[v]]
    print('\n'.join(ans))


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

links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

solve(n, m, links)


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 5)


def solve(n, m, links):
    if m % 2 == 1:
        print(-1)
        return

    tree = [set() for _ in range(n)]
    parents = [-1] * n
    q = deque([0])
    while q:
        v = q.popleft()
        for u in links[v]:
            if parents[u] == -1:
                tree[v].add(u)
                parents[u] = v
                q.append(u)
            links[u].remove(v)

    parities = [len(l) % 2 for l in links]

    # print(links)
    # print(tree)
    # print(parents)
    # print(parities)

    def dfs(v):
        b = parities[v]
        for u in tree[v]:
            c = dfs(u)
            b ^= c
        if b:
            p = parents[v]
            links[p].remove(v)
            links[v].add(p)
        return b

    dfs(0)

    ans = ['{} {}'.format(v + 1, u + 1) for v in range(n) for u in links[v]]
    print('\n'.join(ans))


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

links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

solve(n, m, links)
### BUGGY CODE ###

N, W = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1 for _ in range(W+1)] for _ in range(N)]

# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値を返す
def f(i, j):
    # 終了条件
    if i == N:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    w, v = w_v[i]

    # これ以上入らないとき
    if j - w < 0:
        dp[i][j] = f(i+1, j)

    # まだ入るときは両方試す
    else:
        dp[i][j] = max(f(i+1, j), f(i+1, j-w)+v)
    return dp[i][j]

print(f(0, W))


### FIXED CODE ###

N, W = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(N)]


# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    w, v = w_v[i]
    for j in range(W+1):
        if j - w >= 0:
            dp[i+1][j] = max(dp[i][j-w]+v, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(max(dp[N]))
### BUGGY CODE ###

N = int(input())

A_list = [int(_) for _ in input().split()]

ans = 0
for i in range(len(A_list)):
    if i <= N-1:
        if A_list[i] == 0:
            continue
        j = i+1
        ans += sum(map(lambda x:x*A_list[i]%(10**9+7), A_list[j:N]))
        ans = ans%(10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
A_list = [int(_) for _ in input().split()]

c = 10**9+7


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


inv = modinv(2, c)

sum_of_a = sum(A_list) % c
sum_of_sq_a = sum([i**2 for i in A_list]) % c

ans = (sum_of_a**2 % c - sum_of_sq_a)*inv %c

print(ans)