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

import collections
import sys
sys.setrecursionlimit(10**7)

def calc(zero,one,two,three):
  n=zero+one+two+three
  if (zero,one,two,three) in memo:
    return memo[(zero,one,two,three)]
  ret=0
  if zero!=n:
    ret=1/(1-zero/n)
  if one!=0:
    ret+=(calc(zero+1,one-1,two,three)*one/n)/(1-zero/n)
  if two!=0:
    ret+=(calc(zero,one+1,two-1,three)*two/n)/(1-zero/n)
  if three!=0:
    ret+=(calc(zero,one,two+1,three-1)*three/n)/(1-zero/n)
  memo[(zero,one,two,three)]=ret
  return ret

n=int(input())
arr=list(map(int,input().split()))
memo=collections.defaultdict(int)
cnt=[0,0,0,0]
for val in arr:
  cnt[val]+=1
calc(cnt[0],cnt[1],cnt[2],cnt[3])
print(memo[(cnt[0],cnt[1],cnt[2],cnt[3])])

### FIXED CODE ###

import collections

n=int(input())
arr=list(map(int,input().split()))
dp=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
cnt=collections.Counter(arr)
for total in range(1,n+1):
  for three in range(total+1):
    for two in range(total-three+1):
      one=total-two-three
      dp[one][two][three]+=n/total
      if one!=0:
        dp[one][two][three]+=dp[one-1][two][three]*one/total
      if two!=0:
        dp[one][two][three]+=dp[one+1][two-1][three]*two/total
      if three!=0:
        dp[one][two][three]+=dp[one][two+1][three-1]*three/total
print(dp[cnt[1]][cnt[2]][cnt[3]])
### BUGGY CODE ###

from functools import reduce
while True:
    n = input()
    if n == '0000': break
    if len(n) < 4: n = n.zfill(4)
    if reduce(lambda x,y: x and y, [n[0] == s for s in n]):
        print('NA')
    else:
        cnt = 0
        while n != '6174':
            s = ''.join(sorted(n))
            l = s[::-1]
            n = str(int(l)-int(s))
            if len(n) < 4: n.zfill(4)
            cnt += 1
        print(cnt)

### FIXED CODE ###

from functools import reduce
while True:
    n = input()
    if n == '0000': break
    if len(n) < 4: n = n.zfill(4)
    if reduce(lambda x,y: x and y, [n[0] == s for s in n]):
        print('NA')
    else:
        cnt = 0
        while n != '6174':
            s = ''.join(sorted(n))
            l = s[::-1]
            n = str(int(l)-int(s))
            if len(n) < 4: n = n.zfill(4)
            cnt += 1
        print(cnt)
### BUGGY CODE ###

S = list(input())
N = len(S)
num = 0
cnt = [0]*2019
cnt[0] = 1
#T[i]: i+1文字目以降を数とみなしたときの数
for i in range(N-1, -1, -1):
    d = 10 ** (N-i-1)
    num += int(S[i]) * d
    num %= 2019
    # num = (num + int(S[i]) * 10 ** (N- i -1)) % 2019
    cnt[num] += 1

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

### 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 ###


import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    H, W = read_values()
    F = [input().strip() for _ in range(H)]
    S = set()
    Q = queue.Queue()

    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                Q.put((h, w, 0))
                S.add((h, w))

    res = V(max)
    while not Q.empty():
        h, w, d = Q.get()
        res.ud(d)

        for hh, ww in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= hh < H and 0 <= ww < W:
                if (hh, ww) in S:
                    continue
                Q.put((hh, ww, d + 1))
                S.add((hh, ww))
    
    print(res)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    H, W = read_values()
    F = [input().strip() for _ in range(H)]
    A = [False] * (H * W)
    Q = deque() 

    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                Q.append((h, w, 0))
                A[h * W + w] = True

    res = V(max)
    while Q:
        h, w, d = Q.popleft()
        res.ud(d)

        for hh, ww in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= hh < H and 0 <= ww < W:
                if A[hh * W + ww]:
                    continue
                Q.append((hh, ww, d + 1))
                A[hh * W + ww] = True
    
    print(res)


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

from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    global cnt
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

li = []

for i in range(n):
    tmp = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    li.append(int(tmp, 2))

for x in li:
    print(rec(x))

### FIXED CODE ###

from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


ret = [rec(x) for x in range(2 * 10**5 + 1)]


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)

cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)


li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(ret[x] + 1)

print(*ans, sep="\n")
### BUGGY CODE ###

S = list(input())
N = len(S)
S = [None] + S + [None]
nxt = [i + 1 for i in range(N+2)]
prv = [i - 1 for i in range(N+2)]

def remove(i):
    prv[nxt[i]] = prv[i]
    nxt[prv[i]] = nxt[i]

def dump():
    print(S)
    print(nxt)
    print(prv)
    print()

count = 0
while(True):
    i = nxt[0]
    j = nxt[i]
    removed = False
    while(True):
        #print(i, j)
        #dump()
        if S[i] == None or S[j] == None:
            break
        if S[i] == S[j]:
            i = j
            j = nxt[j]
        else:
            remove(i)
            remove(j)
            removed = True
            count += 2
            i = nxt[prv[i]]
            j = nxt[i]
    if not removed:
        break
#dump()
print(count)

### FIXED CODE ###

S = input()
red_count = S.count('0')
blue_count = S.count('1')
print(min(red_count, blue_count) * 2)
### BUGGY CODE ###

import numpy as np

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

for i in range(0, N):
    a, b = np.array(list(map(float, input().split())))
    A.append(a)
    B.append(b)

cnt = 0
sum = 0
flag = 0
inf = float('inf')
arrayA = np.array(A)
arrayB = np.array(B)
for j in range(0, N):
    idx = A.index(min(arrayA))
    pay = arrayA[idx]
    num = arrayB[idx]
    arrayA[idx]=inf
    if cnt + num < M :
        cnt += num
        sum += pay*num
    else :
        diff = int(M - cnt)
        for t in range(0, diff):
            sum += pay
            cnt += 1
            if cnt == M :
                flag = 1
                print(int(sum))
                break
    if flag == 1:
        break



### FIXED CODE ###

import numpy as np

N, M = map(int, input().split())
A = []

for i in range(0, N):
    a, b = np.array(list(map(float, input().split())))
    A.append((a, b))

dtype = [('key', int), ('value', int)]
arrayA = np.array(A, dtype=dtype)
arrayA = np.sort(arrayA, order=['key'])
cnt = 0
sum = 0
flag = 0
for j in range(0, N):
    pay = arrayA[j][0]
    num = arrayA[j][1]
    if cnt + num < M :
        cnt += num
        sum += pay*num
    else :
        diff = int(M - cnt)
        for t in range(0, diff):
            sum += pay
            cnt += 1
            if cnt == M :
                flag = 1
                print(int(sum))
                break
    if flag == 1:
        break
### BUGGY CODE ###

from sys import stdin

n, *a = map(int, stdin.read().split())
lengths = sorted(set(a), reverse=1)
a.sort()

remainder = 4
long_side, short_side = 0, 0
for l in lengths:
    th = a.index(l)
    c = len(a) - th
    if c != 1:
        if remainder == 4:
            if c >= 4:
                print(l ** 2)
                exit()
            else:
                remainder = 2
                long_side = l
        else:
            short_side = l
            break
    a = a[:th]

print(long_side * short_side)

### FIXED CODE ###

from sys import stdin

n, *a = map(int, stdin.read().split())    
a.sort(reverse=1)

l_count = {}
for l in a:
    l_count.update({l: l_count.get(l, 0) + 1})
  
long_side, short_side = 0, 0
for l, c in sorted(l_count.items(), reverse=1):
    if c != 1:
        if not long_side:
            if c >= 4:
                print(l ** 2)
                exit()
            else:
                long_side = l
        else:
            short_side = l
            break

print(long_side * short_side)
### BUGGY CODE ###

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


def delitable(numbers):
    return [v for i, v in enumerate(numbers) if v == i + 1]


b_searched = set()
b_unsearched = []


b_searched.add(tuple(b))
delit = delitable(b)

if delit == []:
    print("-1")
for delit_num in delit:
    b_unsearched.append([b[:delit_num - 1] + b[delit_num:], [delit_num]])


while b_unsearched:
    b, log = b_unsearched.pop()

    if b and max(b) > N - len(log):
        continue

    b_tuple = tuple(b)
    b_searched.add(b_tuple)
    delit = delitable(b)


    if not delit:
        if not b:
            log.reverse()
            print("\n".join(map(str, log)))
            break
        else:
            continue
    for delit_num in delit:
        b_temp = b[:delit_num - 1] + b[delit_num:]
        if not tuple(b_temp) in b_searched:
            b_unsearched.append([b_temp, log + [delit_num]])
else:
    print("-1")

### FIXED CODE ###

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


def delitable(numbers):
    return [v for i, v in enumerate(numbers) if v == i + 1]


log = []
while b:
    delit = delitable(b)
    if not delit:
        print(-1)
        break
    del b[delit[-1] - 1]
    log.append(delit[-1])
else:
    log.reverse()
    print("\n".join(map(str, log)))
### BUGGY CODE ###

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

li = [[0 for _ in range(N+1)] for _ in range(W+1)]

for n in range(1,N+1):
    for w in range(W+1):
        if w>=w_li[n-1][0]:
            li[w][n] = max(li[w][n-1] , li[w-w_li[n-1][0]][n-1]+w_li[n-1][1])
        else:
            li[w][n] = li[w][n-1]
print(li[W][N])

### FIXED CODE ###

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

li = [[0 for _ in range(N+1)] for _ in range(W+1)]

for n in range(1,N+1):
    for w in range(W+1):
        if w>=w_li[n-1][0]:
            li[w][n] = max(li[w][n-1] , li[w-w_li[n-1][0]][n-1]+w_li[n-1][1])
        else:
            li[w][n] = li[w][n-1]
print(li[W][N])
### BUGGY CODE ###

def primeq(x):
    if x==1:return False
    for i in range(2,x):
        if x%i==0:return False
    return True

c=0
for i in range(int(input())):
    if primeq(int(input())):c+=1
print(c)


### FIXED CODE ###

def primeq(x):
    if x==1:return False
    for i in range(2,int(x**.5)+1):
        if x%i==0:return False
    return True

c=0
for i in range(int(input())):
    if primeq(int(input())):c+=1
print(c)
### BUGGY CODE ###

s = input()
a = [0] * len(s)
for i in range(len(s)):
  ct = 0
  if(s[i] == 'R'):
    k = i + 1
    ct += 1
    while(s[k] != 'L'):
      k += 1
      ct += 1
    if(ct % 2 == 0):
      a[k] += 1
    else:
      a[k-1] += 1
  else:
    k = i - 1
    ct += 1
    while(s[k] != 'R'):
      k -= 1
      ct += 1
    if(ct % 2 == 0):
      a[k] += 1
    else:
      a[k+1] += 1

num = [str(i) for i in a]
print(" ".join(num))

### FIXED CODE ###

s = input()
a = [0] * len(s)
i = 0
while(i < len(s)):
  if(s[i] == 'R'):
    k = i + 1
    while(s[k] != 'L'):
      k += 1
    a[k] += (k-i)//2
    a[k-1] += k-i-(k-i)//2
    i = k
  i += 1
j = len(s) -1
while(j >= 0):
  if(s[j] == 'L'):
    l = j-1
    while(s[l] != 'R'):
      l -= 1
    a[l] += (j-l)//2
    a[l+1] += j-l- (j-l)//2
    j = l
  j -= 1
num = [str(i) for i in a]
print(" ".join(num))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
def solve(v):
    t=[]
    for u in e[v]:
        if not f[u]:
            f[u]=1
            t=solve(u)+t
            break
    return [v]+t
n,m,*t=map(int,open(0).read().split())
e=[[]for _ in range(n+1)]
for a,b in zip(t[::2],t[1::2]):
    e[a].append(b)
    e[b].append(a)
f=[0]*-~n
f[1]=1
a=solve(1)[:0:-1]+solve(1)
print(len(a),*a)

### FIXED CODE ###

n,m,*t=map(int,open(0).read().split())
e=[[]for _ in range(n+1)]
for a,b in zip(t[::2],t[1::2]):
    e[a].append(b)
    e[b].append(a)
f=[0]*-~n
f[1]=1
a=[1]
while 1:
    for v in e[a[-1]]:
        if not f[v]:
            f[v]=1
            a.append(v)
            break
    else:
        break
b=[1]
while 1:
    for v in e[b[-1]]:
        if not f[v]:
            f[v]=1
            b.append(v)
            break
    else:
        break
a=a[:0:-1]+b
print(len(a),*a)
### BUGGY CODE ###

from collections import defaultdict
mod = 10**9+7
N, M = map(int, input().split())
S = "".join(input().split())
T = "".join(input().split())
dS = defaultdict(int)
dT = defaultdict(int)
dS[""] += 1
dT[""] += 1
for i in range(N):
    newkey = []
    for key in dS:
        newkey.append((key+S[i], dS[key]))
    
    for key, c in newkey:
        dS[key] += c

for i in range(M):
    newkey = []
    for key in dT:
        newkey.append((key+T[i], dT[key]))

    for key, c in newkey:
        dT[key] += c

    

ans = 0
for key in dS:
    ans += dS[key]*dT[key]%mod

print(ans%mod)


### FIXED CODE ###

mod = 10**9 + 7
N, M = map(int, input().split())
S = [None] + list(map(int, input().split()))
T = [None] + list(map(int, input().split()))
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        if S[i] == T[j]:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j] + 1)%mod
        else:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1])%mod
print((dp[N][M]+1)%mod)
### BUGGY CODE ###

s = [int(e) for e in input().split()]
x = int(s[0])
y = int(s[1])
a = int(s[2])
b = int(s[3])
c = int(s[4])
a_l = [int(e) for e in input().split()]
b_l = [int(e) for e in input().split()]
c_l = [int(e) for e in input().split()]

a_l.sort(reverse=True)
b_l.sort(reverse=True)
c_l.sort(reverse=True)

apple = []
app=a_l[0:x]+b_l[0:y]
app.sort()

for c_app in c_l:
    if app[0]<c_app:
        app[0]=c_app
    app.sort()

apple_count=sum(app)

print(apple_count)

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
x, y, a, b, c = nm()
p = nl()
q = nl()
r = nl()
p.sort()
q.sort()
l = p[-x:] + q[-y:]
l.sort()
r.sort()
for i in range(c):
    if l[i] < r[-1]:
        l[i] = r.pop()
    else:
        break
print(sum(l))
### BUGGY CODE ###

A, B, N = map(int, input().split())
ans_list = []
for x in range(N + 1):
    ans_list.append(((A * x) // B) - (A * (x // B)))


print(max(ans_list))

### FIXED CODE ###

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

if N >= B:
    x = B - 1
    ans = ((A * x) // B) - (A * (x // B))
else:
    x = N
    ans = ((A * x) // B) - (A * (x // B))


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

N = int(input())
S = input()
count = 0
def findlet(let,ind):
    add = st[ind:].count(let)
    if add > 0:
        if 2*ind < len(st):
            if st[2*ind] == let:
                add -= 1
        global count
        count += add
for i in range(N-2):
    st = S[i:]
    if st[0] == "R":
        for j in [x for x, y in enumerate(st) if y == 'G']:
            findlet("B",j)
        for j in [x for x, y in enumerate(st) if y == 'B']:
            findlet("G",j)
    elif st[0] == "G":
        for j in [x for x, y in enumerate(st) if y == 'B']:
            findlet("R",j)
        for j in [x for x, y in enumerate(st) if y == 'R']:
            findlet("B",j)
    else:
        for j in [x for x, y in enumerate(st) if y == 'R']:
            findlet("G",j)
        for j in [x for x, y in enumerate(st) if y == 'G']:
            findlet("R",j)
print(count)

### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
count = r * g * b
for i in range(N):
    for j in range(i+1,N-1):
        if 2*j - i <= N-1:
            l = set([S[i],S[j],S[2*j-i]])
            if len(l) == 3:
                count -= 1
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

def solve():
    N, M = map(int, input().split())
    dp = np.array([-1]*2**N, dtype=np.uint32)
    dp[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        d = sum(2**(c-1) for c in  map(int, input().split()))
        for j,e in enumerate(dp):
            if d|j == d:
                dp[j] = min(e,a)
            else:
                k = j-(j&d)
                dp[j] = min(e, dp[k]+a)

    res = dp[-1] if dp[-1] < np.uint32(-1) else -1
    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

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

def solve():
    N, M = map(int, input().split())
    max_int = 2**32-1
    dp = [max_int]*2**N
    dp[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        d = sum(2**c for c in map(int, input().split()))>>1
        for j in range(2**N+1):
            if j|d == d:
                dp[j] = min(dp[j],a)
            elif j&d:
                dp[j] = min(dp[j], dp[j-(j&d)]+a)

    res = dp[-1] if dp[-1] < max_int else -1
    return str(res)

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

N,M = map(int,input().split())
es = [[] for i in range(N)]
for i in range(M):
    l,r,d = map(int,input().split())
    l,r = l-1,r-1
    es[l].append((r,d))
    es[r].append((l,-d))

checked = [0] * N
for i in range(N):
    if checked[i]: continue
    dist = [None] * N
    dist[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        checked[v] = 1
        for to,d in es[v]:
            if dist[to] is None:
                dist[to] = dist[v] + d
                if not checked[to]:
                    stack.append(to)
            else:
                if dist[to] != dist[v] + d:
                    print('No')
                    exit()
print('Yes')

### FIXED CODE ###

N,M = map(int,input().split())
es = [[] for i in range(N)]

for i in range(M):
    l,r,d = map(int,input().split())
    l,r = l-1, r-1
    es[l].append((r,d))
    es[r].append((l,-d))

dist = [None] * N
for i in range(N):
    if dist[i] is not None: continue
    stack = [i]
    dist[i] = 0
    while stack:
        v = stack.pop()
        for to,d in es[v]:
            if dist[to] is None:
                stack.append(to)
                dist[to] = dist[v] + d
            elif dist[to] != dist[v] + d:
                print('No')
                exit()
print('Yes')
### BUGGY CODE ###

import math
A,B,N = list(map(int,input().split()))
ans = 0
c = int()
for i in range(N+1):
    c = math.floor(A*i/B)-(A*math.floor(i/B))
    if ans <= c:
        ans  =c
print(ans)

### FIXED CODE ###

import math
A,B,N = list(map(int,input().split()))
c = int()
if B-1 > N:
    i = N
else:
    i = B-1
c = math.floor(A*i/B)-(A*math.floor(i/B))

print(c)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
inf=10**10

def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


def f(s):
    r=[]
    for j in range(W):
        if s[j]=="#": r.append(inf)
        elif s[j]==".": r.append(0)
    return r

H,W=map(int,input().split())
x=[f(input()) for i in range(H)]

cost = [[float("inf") for i in range(H*W)] for i in range(H*W)] 
for i in range(H*W):
    for j in range(H*W):
        if x[i//W][i%W]==inf or x[j//W][j%W]==inf: continue
        if abs(i-j)==W: cost[i][j],cost[j][i]=1,1
        elif i-j==1 and i%W!=0: cost[i][j],cost[j][i]=1,1
        elif j-i==1 and j%W!=0: cost[i][j],cost[j][i]=1,1

ans=0
for i in range(H):
    for j in range(W):
        if x[i][j]==0: ans+=1

ans-=dijkstra(0,H*W,cost)[H*W-1]+1
print(ans if ans>=0 else -1)

### FIXED CODE ###

import sys
from collections import deque

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
        return -1

    except RuntimeError:
        print(-1)
        sys.exit()


H,W=map(int,input().split())
m=[input() for i in range(H)]

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
p=bfs(m,visited)
print( p if p==-1 else ans-p-1)
### BUGGY CODE ###

N, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
ans = []

for i in range(N):
  ans += [ab[i][0]] * ab[i][1]

ans.sort()
print(ans[K-1])

### FIXED CODE ###

N, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
ab.sort()

n = 0
for i in range(N):
  if n + ab[i][1] < K:
    n += ab[i][1]
  else:
    print(ab[i][0])
    break
### BUGGY CODE ###

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

mod=10**9+7

total = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        total += A[i]*A[j]
        total%=mod
print(total)


### FIXED CODE ###

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

mod = 10 ** 9 + 7

sum_a=0
for i in A:
    sum_a+=i
    sum_a%=mod

total=0
for i in range(N - 1):
    sum_a -= A[i]
    total+=A[i]*(sum_a)
    total%=mod
print(total)