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

import itertools

H, W = map(int, input().split())
s = [""] * H
for i in range(H):
  s[i] = input()

res = H*W
induce = ["r"]*(H-1) + ["c"]*(W-1)
M = len(induce)
perm_iter = itertools.permutations(induce)
for i, perm in enumerate(perm_iter):
  route = ""
  r, c = 0, 0
  route += s[0][0]
  for j in range(M):
    if perm[j] == "r":
      r += 1
    elif perm[j] == "c":
      c += 1
    route += s[r][c]
  
  cnt = route.split(".")
  cnt = len(cnt) - cnt.count("")
  if cnt < res:
    res = cnt
  
print(res)  


### FIXED CODE ###

H, W = map(int, input().split())
s = [""] * H
for h in range(H):
  s[h] = input()

INF = float('inf')
dp = [[[INF, s[h][w]] for w in range(W)] for h in range(H)]

def update_dp_1(c, dp):
  if dp[1] == ".":
    if c == ".":
      res = [dp[0], "."]
    else:  # c == "#"
      res = [dp[0]+1, "#"]
  else:  # dp[1] == "#"
    if c == ".":
      res = [dp[0], "."]
    else:  # c == "#"
      res = [dp[0], "#"]
  return res

def update_dp_2(c, dp_a, dp_b):
  a = update_dp_1(c, dp_a)
  b = update_dp_1(c, dp_b)
  if a[0] < b[0]:
    return a
  else:
    return b

if s[0][0] == ".":
  dp[0][0] = [0, "."]
else:  #  == "#"
  dp[0][0] = [1, "#"]

for h in range(H):
  if h != 0:
    dp[h][0] = update_dp_1(dp[h][0][1], dp[h-1][0])
  for w in range(1, W):
    if h == 0:
      dp[h][w] = update_dp_1(dp[h][w][1], dp[h][w-1])
    else:
      dp[h][w] = update_dp_2(dp[h][w][1], dp[h-1][w], dp[h][w-1])

print(dp[H-1][W-1][0])
### BUGGY CODE ###

mod = 998244353
n,k = map(int,input().split())
K = [list(map(int,input().split())) for i in range(k)]

dp = [0]*(n+1)
dp[0] = 1
dp2 = [0]*(n+1)
for i in range(n):
    dp2[i] = (dp2[i]+dp2[i-1])%mod
    dp[i] = (dp[i]+dp2[i])%mod
    for l,r in K:
        dp2[min(i+l,n)] = (dp2[min(i+l,n)]+dp[i])%mod
        dp2[min(i+r+1,n)] = (dp2[min(i+r+1,n)]-dp[i])%mod
print(dp[n-1]%mod)


### FIXED CODE ###

mod = 998244353
n,k = map(int,input().split())
K = [list(map(int,input().split())) for i in range(k)]

dp = [0]*(n+5)
dp[1] = 1
dp2 = [0]*(n+5)
for i in range(1,n+1):
    dp[i] = (dp[i]+dp2[i]+dp2[i-1])%mod
    dp2[i] = (dp2[i]+dp2[i-1])%mod
    for l,r in K:
        dp2[min(i+l,n+2)] += dp[i]
        dp2[min(i+l,n+2)] %= mod
        dp2[min(i+r+1,n+2)] -= dp[i]
        dp2[min(i+r+1,n+2)] %= mod
print(dp[n]%mod)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
a = [[0] * W for _ in range(H)]
q = deque([])
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            a[i][j] = 1
            q.appendleft((i, j, 0))

while True:
    try:
        i, j, val = q.pop()
        if i > 0 and a[i - 1][j] == 0:
            q.appendleft((i - 1, j, val + 1))
            a[i - 1][j] = 1
        if i < H - 1 and a[i + 1][j] == 0:
            q.appendleft((i + 1, j, val + 1))
            a[i + 1][j] = 1
        if j > 0 and a[i][j - 1] == 0:
            q.appendleft((i, j - 1, val + 1))
            a[i][j - 1] = 1
        if j < W - 1 and a[i][j + 1] == 0:
            q.appendleft((i, j + 1, val + 1))
            a[i][j + 1] = 1
    except:
        print(val)
        break

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
a = [[0] * W for _ in range(H)]
q = deque([])
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            a[i][j] = 1
            q.appendleft((i, j, 0))

while True:
    try:
        i, j, val = q.pop()
        if i > 0 and a[i - 1][j] == 0:
            q.appendleft((i - 1, j, val + 1))
            a[i - 1][j] = 1
        if i < H - 1 and a[i + 1][j] == 0:
            q.appendleft((i + 1, j, val + 1))
            a[i + 1][j] = 1
        if j > 0 and a[i][j - 1] == 0:
            q.appendleft((i, j - 1, val + 1))
            a[i][j - 1] = 1
        if j < W - 1 and a[i][j + 1] == 0:
            q.appendleft((i, j + 1, val + 1))
            a[i][j + 1] = 1
    except:
        print(val)
        break
### BUGGY CODE ###

N, x = map(int, input().split())
A = list(map(int, input().split())) * 2
A = A[::-1]

effective_costs = [float('inf')] * N
ans = float('inf')

# 魔法を使う回数
for k in range(N):
    cost = 0
    for i in range(N):
        effective_costs[i] = min(effective_costs[i], A[i+k])
        cost += effective_costs[i]
    ans = min(ans, cost + k * x)

print(ans)


### FIXED CODE ###

N, x = map(int, input().split())
A = list(map(int, input().split()))
lowest_costs = A[:]
ans = float('inf')

for k in range(N):
    lowest_costs = [min(lowest_costs[i], A[i-k]) for i in range(N)]
    ans = min(sum(lowest_costs) + x * k, ans)

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

def main():
    N, M = map(int, input().split())

    i = 0
    AB = []
    while i < M:
        a, b = map(int, input().split())
        AB += [a, b]
        i += 1

    i = 1
    while i <= N:
        if AB.count(i) % 2 > 0:
            print('NO')
            break
        i += 1
    else:
        print('YES')

main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())

    i = 0
    AB = [0 for i in range(N)]
    while i < M:
        a, b = map(int, input().split())
        AB[a-1] += 1
        AB[b-1] += 1
        i += 1

    for i in AB:
        if i % 2 > 0:
            print('NO')
            break
    else:
        print('YES')

main()
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split(" ")))
for i in range(1,n+1):
    c=0
    for j in range(len(l)):
        if l[j]==i:
            l[j]=0
            c+=1
    print(c)
    for j in range(c):
        l.remove(0)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split(" ")))
s=[0]*n
for i in range(len(l)):
    s[l.pop()-1]+=1
    
for i in range(n):
    print(s[i])
### BUGGY CODE ###

from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

for i in range(n):
  v=a[i]
  if is_p[v]:
    for j in range(v+v,10**6+1,v):
#      print(j)
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)

### FIXED CODE ###

from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

for i in set(a):
  v=i
  if is_p[v]:
    for j in range(v+v,10**6+1,v):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)
### BUGGY CODE ###

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

p = len(format(max(A), 'b'))
digit = '0' + str(p) + 'b'
#S = list(map(format, A, digit))

r = [0] * p
for a in A:
  s = format(a, digit)
  for j in range(p):
    r[j] += int(s[j])

res = 0
for j in range(p):
  res += r[j] * (N - r[j]) * (2 ** (p-1-j))

print(res % (10**9 + 7))

### FIXED CODE ###

import numpy as np 
N = int(input())
A = np.fromstring(input(), dtype = np.int64, sep = ' ')

res = 0
for bit in range(60):
  c = int((A & 1).sum())
  res += c * (N - c) * (1 << bit)
  A >>= 1

print(res % 1000000007)
### BUGGY CODE ###

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


counts = [0] * 20

res = 0
left = 0
right = 0

r = bin(A[right])
for i in range(len(r)-2):
    counts[i] += int(r[-(i+1)])

while left < N and right < N:
    if max(counts) >= 2:
        r = bin(A[left])
        for i in range(len(r)-2):
            counts[i] -= int(r[-(i+1)])
        left += 1
    else:
        res += right - left + 1
        # print(left, right)
        right += 1
        if right < N:
            r = bin(A[right])
            for i in range(len(r)-2):
                counts[i] += int(r[-(i+1)])

print(res)

### FIXED CODE ###

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

counts = [0] * 20

res = 0
left = 0
right = 0

r = bin(A[right])
for i in range(len(r)-2):
    counts[i] += int(r[-(i+1)])

while left < N and right < N:
    if max(counts) >= 2:
        r = bin(A[left])
        for i in range(len(r)-2):
            counts[i] -= int(r[-(i+1)])
        left += 1
    else:
        res += right - left + 1
        # print(left, right)
        right += 1
        if right < N:
            r = bin(A[right])
            for i in range(len(r)-2):
                counts[i] += int(r[-(i+1)])

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

n, m = [int(item) for item in input().split()]
INF = 10 ** 10
dp = [INF] * (2 ** n)
dp[0] = 0
for i in range(m):
    a, b = [int(item) for item in  input().split()]
    c = [int(item) - 1 for item in  input().split()]
    bit = 0
    for item in c:
        bit |= 1 << item
    for j in range(2 ** n):
        dp[j | bit] = min(dp[j | bit], dp[j] + a)
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

n, m = [int(item) for item in input().split()]
INF = 10 ** 10
dp = [INF] * (2 ** n)
dp[0] = 0
for i in range(m):
    a, b = [int(item) for item in  input().split()]
    c = [int(item) - 1 for item in  input().split()]
    bit = 0
    for item in c:
        bit |= 1 << item
    for j in range(2 ** n):
        dp[j | bit] = min(dp[j | bit], dp[j] + a)
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

ans = 0
S = set()
N = int(input())
s_list = [''.join(sorted(input())) for _ in range(N)]
for i in range(len(s_list)-1):
    for j in range(i+1, len(s_list)):
        if s_list[i] == s_list[j]:
            ans += 1
print(ans)

### FIXED CODE ###

ans = 0
N = int(input())
s_list = [''.join(sorted(input())) for _ in range(N)]
s_list.sort()

count = 1
for i in range(1, N):
    if s_list[i] == s_list[i-1]:
        count += 1
    else:
        ans += (count*(count-1))/2
        count = 1

    if i == N-1:
        ans += (count*(count-1))/2

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

import math
from functools import reduce
K = int(input())
s = []
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(K):
    for j in range(K):
        for k in range(K):
            s.append(gcd(i+1,j+1,k+1))
print(sum(s))

### FIXED CODE ###

import math
from functools import reduce
K = int(input())
s = []
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(K):
    for j in range(K):
        for k in range(K):
            s.append(gcd(i+1,j+1,k+1))
print(sum(s))
### BUGGY CODE ###

h, w, m = map(int, input().split())
h_l = [[] for i in range(h + 1)]
w_l = [[] for i in range(w + 1)]
max_h = 0
max_h_l = []
max_w = 0
max_w_l = []
inputs = {}
for _ in range(m):
    h, w = map(int, input().split())
    inputs.setdefault(h, set([w]))
    inputs[h].add(w)

    if h_l[h] :
        h_l[h][1].add(w)
        h_l[h][0] += 1
    else:
        h_l[h] = [1, set([w])]
        
    if h_l[h][0] > max_h:
        max_h_l = [h]
        max_h = h_l[h][0]
    elif h_l[h][0] == max_h:
        max_h_l.append(h)
 
        
    if w_l[w]:
        w_l[w][1].add(h)
        w_l[w][0] += 1
    else:
        w_l[w] = [1, set([h])]
    if w_l[w][0] > max_w:
        max_w_l = [w]
        max_w = w_l[w][0]
    elif w_l[w][0] == max_w:
        max_w_l.append(w)

ans = max_h + max_w -1
flag = 0
for i in max_h_l:
    if flag == 1:
        break
    for j in max_w_l:
        if j not in inputs[i]:
            ans = max_h + max_w
            flag = 1
            break
        
print(ans)

### FIXED CODE ###

h, w, m = map(int, input().split())
h_l = [[] for i in range(h + 1)]
w_l = [[] for i in range(w + 1)]
max_h = 0
max_h_l = []
max_w = 0
max_w_l = []
inputs = {}
for _ in range(m):
    h, w = map(int, input().split())
    inputs.setdefault(h, set([w]))
    inputs[h].add(w)

    if h_l[h] :
        h_l[h][1].add(w)
        h_l[h][0] += 1
    else:
        h_l[h] = [1, set([w])]
        
    if h_l[h][0] > max_h:
        max_h_l = [h]
        max_h = h_l[h][0]
    elif h_l[h][0] == max_h:
        max_h_l.append(h)
 
        
    if w_l[w]:
        w_l[w][1].add(h)
        w_l[w][0] += 1
    else:
        w_l[w] = [1, set([h])]
    if w_l[w][0] > max_w:
        max_w_l = [w]
        max_w = w_l[w][0]
    elif w_l[w][0] == max_w:
        max_w_l.append(w)

ans = max_h + max_w -1
flag = 0
for i in max_h_l:
    if flag == 1:
        break
    for j in max_w_l:
        if j not in inputs[i]:
            ans = max_h + max_w
            flag = 1
            break
        
print(ans)
### BUGGY CODE ###

import numpy as np
n=int(input())
s=list(input())
sr=set()
sg=set()
sb=set()
for ii in range(n):
    if s[ii]=="R":
        sr.add(ii)
    if s[ii]=="G":
        sg.add(ii)
    if s[ii]=="B":
        sb.add(ii)
r=0
for ii in sr:
  for jj in sg:
    for kk in sb:
      if abs(ii-jj)!=abs(jj-kk) and abs(jj-kk)!=abs(kk-ii) and abs(kk-ii)!=abs(ii-jj):
        r+=1
print(r)

### FIXED CODE ###

import numpy as np
n=int(input())
s=list(input())
sr=set()
sg=set()
sb=set()
for ii in range(n):
    if s[ii]=="R":
        sr.add(ii)
    if s[ii]=="G":
        sg.add(ii)
    if s[ii]=="B":
        sb.add(ii)
l=[len(sr),len(sg),len(sb)]
l.sort()

if l[0]==len(sr):
  s1=sr
  if l[1]==len(sg):
    s2=sg
    s3=sb
  else:
    s2=sb
    s3=sg
elif l[0]==len(sg):
  s1=sg
  if l[1]==len(sr):
    s2=sr
    s3=sb
  else:
    s2=sb
    s3=sr
else:
  s1=sb
  if l[1]==len(sr):
    s2=sr
    s3=sg
  else:
    s2=sg
    s3=sr
  
r=0
for ii in s1:
  for jj in s2:
    r+=len(s3)
    dt=abs(ii-jj)
    if ii+dt in s3:
      r-=1
    if ii-dt in s3:
      r-=1
    if jj+dt in s3:
      r-=1
    if jj-dt in s3:
      r-=1
    if (ii+jj)%2==0:
      if (ii+jj)//2 in s3:
        r-=1
      
print(r)
### BUGGY CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
#template
#issueから始める
N,X,Y = inputlist()
graph = [[0]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if i - j == 1 or j - i == 1:
            graph[i][j] = 1
            graph[j][i] = 1
        if i == X and j == Y or i == Y and j == X:
            graph[X][Y] = 1
            graph[Y][X] = 1
from scipy.sparse.csgraph import shortest_path
import numpy as np
c = np.array(graph)
path = shortest_path(c,'D')
ans = [0]*(N+1)
for i in range(1,N+1):
    for j in range(1,N+1):
        if path[i,j] != 0:
            ans[int(path[i,j])] +=1
for i in range(1,N):
    print(ans[i]//2)

### FIXED CODE ###

#template
def inputlist(): return [int(j) for j in input().split()]
#template
#issueから始める
N,X,Y = inputlist()
graph = [[] for _ in range(N+1)]
for i in range(1,N):
    graph[i].append(i+1)
    graph[i+1].append(i)
graph[X].append(Y)
graph[Y].append(X)
seen = [False]*(N+1)
ans = [0]*(N+1)
def bfs(i):
    from collections import deque
    que = deque()
    que.append([i,0])
    seen[i] = True
    while len(que)!=0:
        li = que.popleft()
        x = li[0]
        count = li[1]
        for j in graph[x]:
            if seen[j]:
                continue
            seen[j] = True
            counta= count + 1
            que.append([j,counta])
            ans[counta]+=1
for i in range(1,N+1):
    seen = [False]*(N+1)
    bfs(i)
for i in range(1,N):
    print(ans[i]//2)
### BUGGY CODE ###

N = int(input())
A = input()
A = A.split(' ')
X = 1
for i in range(N):
    X *= int(A[i])
if X > 10**18:
    print('-1')
else:
    print(X)

### FIXED CODE ###

def main():
    N = int(input())
    A = input()
    A = A.split(' ')

    for i in A:
        if i == '0':
            print(0)
            return

    X = 1
    for i in A:
        X *= int(i)
        if X > 1000000000000000000:
            print(-1)
            return
    print(X)
main()
### BUGGY CODE ###

N = int(input())

#各都市に行くためのコスト
lift = [int(input()) for i in range(5)]
#各都市にいる人数
city = [0] * 6
city[0] = N

ans = 0
target = []

while 1:
    if city[5] == N:
        break
    for i in range(0,5):
        #今回の操作で動かすもの一覧を作る（i-1に値があるものだけ動かす)
        if city[i] != 0:
            target.append(i+1)
    for i in reversed(target):
        if city[i-1] >= lift[i-1]:
            city[i] += lift[i-1]
            city[i - 1] -= lift[i-1]
        else:
            city[i] += city[i-1]
            city[i-1] = 0
    target = []
    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())

#各都市に行くためのコスト
lift = [int(input()) for i in range(5)]
#各都市にいる人数
city = [0] * 6


print(int((N + min(lift) - 1)  / min(lift) + 4))
### BUGGY CODE ###

n, k, q = map(int, input().split())
l = [k for _ in range(n)]

for i in range(q):
    a = int(input())
    l = list(map(lambda x: x - 1, l))
    l[a - 1] += 1

for j in range(n):
    if l[j] > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

n, k, q = map(int, input().split())
l = [k for _ in range(n)]

l = list(map(lambda x: x - q, l))

for i in range(q):
    a = int(input())
    l[a - 1] += 1

for j in range(n):
    if l[j] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

S = input()
INF = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for l in range(len(S))]
S_li = [_ for _ in S]
S_li = S_li[::-1]
if S_li[0] == '?':
    dp[0][0:10] = [1,1,1,1,1,1,1,1,1,1]
else:
    dp[0][int(S_li[0])] = 1
for _ in range(1,len(S)):
    if S_li[_] == '?':
        for x in range(10):
            for y in range(13):
                dp[_][((x * (10 ** (_ % 6))) + y) % 13] += dp[_ - 1][y] % INF
    else:
        for y in range(13):
            dp[_][((int(S_li[_]) * (10 ** (_ % 6))) + y) % 13] += dp[_ - 1][y] % INF
print(dp[-1][5] % INF)

### FIXED CODE ###

MOD = 1000000007;
 
s = [int(x) if x!="?" else -1 for x in input()]
#print(s)
n=len(s)
 
r=[0]*13
 
c=s[0]
if (c!=-1):
    r[c]=1
else:
    for i in range(10):r[i]=1
for i in range(1,n):
    dp=[0]*26
    for j in range(13):dp[j*10%13]+=(r[j]%MOD)
    dp[13:26]=dp[0:13]
    c=s[i]
    r=[0]*13
    if (c==-1):
        w=sum(dp[4:14])
        for j in range(13):
            r[j]+=w
            w=w+dp[j+1]-dp[4+j]
    else:
        for j in range(13):
            r[j]+=dp[13-c+j]
print (r[5]%MOD)
### BUGGY CODE ###

# encoding: utf-8
S = input()

A = 0
C = S.count("C") # N
q = 0

q_max = S.count("?") # N

ABC = 0
div = 10 ** 9 + 7
for si in S: # N
    if si == "A": A += 1
    elif si == "C": C -= 1
    elif si == "B":
        # ABC = (ABC + (A * C) * (3 ** q_max)) % div
        # ABC = (ABC + (q * C) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (A * (q_max - q)) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (q * (q_max - q)) * (3 ** (q_max - 2))) % div
        ABC = (ABC + (3 * A + q) * (3 * C + q_max - q) * (3 ** (q_max - 2))) % div
    else: # "?"
        # ABC = (ABC + (A * C) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (q * C) * (3 ** (q_max - 2))) % div
        # ABC = (ABC + (A * (q_max - q - 1)) * (3 ** (q_max - 2))) % div
        # ABC = (ABC + (q * (q_max - q - 1)) * (3 ** (q_max - 3))) % div        
        ABC = (ABC + (3 * A + q) * (3 * C + q_max - q - 1) * (3 ** (q_max - 3))) % div
        q += 1
    # print(si, ABC)
    
print(int(ABC))

### FIXED CODE ###

# encoding: utf-8
S = input()

A = 0
C = S.count("C") # N
q = 0

q_max = S.count("?") # N

ABC = 0
div = 10 ** 9 + 7
B_base = 3 ** (q_max - 2) % div
q_base = 3 ** (q_max - 3) % div
for si in S: # N
    if si == "A": A += 1
    elif si == "C": C -= 1
    elif si == "B":
        # ABC = (ABC + (A * C) * (3 ** q_max)) % div
        # ABC = (ABC + (q * C) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (A * (q_max - q)) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (q * (q_max - q)) * (3 ** (q_max - 2))) % div
        ABC = (ABC + (3 * A + q) * (3 * C + q_max - q) * B_base) % div
    else: # "?"
        # ABC = (ABC + (A * C) * (3 ** (q_max - 1))) % div
        # ABC = (ABC + (q * C) * (3 ** (q_max - 2))) % div
        # ABC = (ABC + (A * (q_max - q - 1)) * (3 ** (q_max - 2))) % div
        # ABC = (ABC + (q * (q_max - q - 1)) * (3 ** (q_max - 3))) % div        
        ABC = (ABC + (3 * A + q) * (3 * C + q_max - q - 1) * q_base) % div
        q += 1
    # print(si, ABC)
    
print(int(ABC))
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]

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

### FIXED CODE ###

mod = 10**9 + 7

N = int(input())
A = [int(x) for x in input().split()]
S = sum(A) % mod

ans = 0
for i in range(N):
    S -= A[i]
    if S < 0: S += mod

    ans += S * A[i]
    ans %= mod
print(ans)
### BUGGY CODE ###

import math
n, m = input().split()
N = int(n)
M = int(m)

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

for i in range(M):
    mx = max(A)
    k = A.index(mx)
    A[k] = math.floor(mx / 2)

print(sum(A))


### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))
### BUGGY CODE ###

import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)

sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
# input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    nums = [int(c) for c in input().split()]
    arr = [(num, i) for i, num in enumerate(nums)]
    arr.sort(key=lambda x: -x[0])
    dp = [[0] * (n+1) for _ in range(n+1)]    

    for i in range(n):
        for j in range(n-i):
            a, idx = arr[i+j]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a*(idx-i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + a*(n-1-j-idx))

    print(max(dp[i][n-i] for i in range(n+1)))

### FIXED CODE ###

import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split()), 1),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros(n+1, dtype=np.int)

    for k, (i, a) in enumerate(arr, 1):
        ndp = dp.copy()
        
        add_left = np.abs(np.arange(1, k+1) - i) * a
        ndp[1:k+1] = np.maximum(ndp[1:k+1], dp[:k] + add_left)
        
        add_right = np.abs(np.arange(n-k+1, n+1) - i) * a
        ndp[:k] = np.maximum(ndp[:k], dp[:k] + add_right)

        dp = ndp

    print(dp.max())
### BUGGY CODE ###

import math


def f(A, m, K):
    p = sum([a // m for a in A])
    if p > K:
        return False
    else:
        return True


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


left = 1
right = 10 ** 9 + 1

while math.ceil(left) != math.ceil(right):
    m = (left + right) / 2

    if f(A, m, K):
        right = m
    else:
        left = m


print(math.ceil(m))


### FIXED CODE ###

import math


def f(A, m, K):
    p = sum([a // m for a in A])
    if p > K:
        return False
    else:
        return True


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


left = 0
right = 10 ** 9 + 1

while int(left) != int(right):
    m = (left + right) / 2

    if f(A, m, K):
        right = m
    else:
        left = m


print(math.ceil(m))
### BUGGY CODE ###

# スペース区切りの整数の入力
N,M = map(int, input().split())
LR_list=[]
Card_list=[]

#LR読み込み
for i in range(M):
  LR_list.append([int(e) for e in input().split()])

#初期化
for i in range(N):
  Card_list.append(0)

#LRをCardListに適用
for i in range(M):
  #print("")
  for j in range(LR_list[i][0],LR_list[i][1]+1,1):
    Card_list[j-1]+=1
    #print(j,end="")
    
ans=0
    
for i in range(N):
  if Card_list[i]==M:
    ans+=1
    
print(ans)

### FIXED CODE ###

# スペース区切りの整数の入力
N,M = map(int, input().split())
LR_list=[]
Card_list=[]

Min_L = 1
Max_R = N

#LR読み込み
for i in range(M):
  L,R = map(int, input().split())
  if L>Min_L:
    Min_L=L
  if Max_R>R:
    Max_R=R

if Max_R >= Min_L:
  print(Max_R - Min_L + 1)
else:
  print(0)