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

n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n) if i not in bl]
mod = 1000000007
al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()

    
li = [i for i in l if i>=2]

for i in li:
    al[i] = al[i-1] + al[i-2]
    if al[i] == 0:
        print(0)
        exit()

print(al[-1]%mod)

### FIXED CODE ###

n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n)]
cnt = 0
for num in bl:
    del l[num-cnt]
    cnt +=1
    
mod = 1000000007

al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()
    
li = [i for i in l if i>=2]
for i in li:
    al[i] = al[i-1] + al[i-2]
    if al[i] == 0:
        print(0)
        exit()

print(al[-1]%mod)
### BUGGY CODE ###

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

n = int(input())
a = np.array(input().split(), dtype='int')

ans = ''
count_all = 0

for j in range(n):
    num = a[j]
    count = 0
    for i in range(n):
        if a[i] == num:
            count += 1
    if count != 1:
        ans = 'NO'
        break
    count_all += count
    if count_all >= n:
        break

if ans == 'NO':
    print(ans)
else:
    print('YES')

### FIXED CODE ###

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

n = int(input())
a = np.array(input().split(), dtype='int')

a_sort = np.sort(a)
ans = ''

for i in range(n - 1):
    if a_sort[i] == a_sort[i + 1]:
        ans = 'NO'
        break
    
if ans == 'NO':
    print(ans)
else:
    print('YES')
### BUGGY CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, W = map(int, input().split())
    WV = []
    for _ in range(N):
        w, v = map(int, input().split())
        WV.append((w, v))

    # bfs
    # i, weight, value
    q = deque([(-1, 0, 0)])

    ans = 0
    while q:
        i, w, v = q.popleft()

        for j in range(i + 1, N):
            tmp_w = w + WV[j][0]
            if tmp_w > W:
                continue

            tmp_v = v + WV[j][1]
            if tmp_v > ans:
                ans = tmp_v
            q.append((j, tmp_w, tmp_v))

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import defaultdict
import numpy as np

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, W = map(int, input().split())
    d = defaultdict(list)
    w, v = map(int, input().split())
    w1 = w
    d[w].append(v)
    for _ in range(1, N):
        w, v = map(int, input().split())
        d[w].append(v)

    cumsum = dict()
    L = defaultdict(int)
    for i in range(4):
        w = w1 + i
        d[w].sort(reverse=True)
        c = np.cumsum(d[w])
        cumsum[w] = c
        L[i] = len(d[w])

    ans = 0
    for i in range(L[0] + 1):
        if i != 0:
            v1 = cumsum[w1][i - 1]
        else:
            v1 = 0
        for j in range(L[1] + 1):
            if j != 0:
                v2 = v1 + cumsum[w1 + 1][j - 1]
            else:
                v2 = v1
            for k in range(L[2] + 1):
                if k != 0:
                    v3 = v2 + cumsum[w1 + 2][k - 1]
                else:
                    v3 = v2
                for l in range(L[3] + 1):
                    w = w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l
                    if w > W:
                        continue

                    if l != 0:
                        v4 = v3 + cumsum[w1 + 3][l - 1]
                    else:
                        v4 = v3

                    if v4 > ans:
                        ans = v4

    print(ans)


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

n,m=map(int,input().split())
lrd=[list(map(int,input().split())) for _ in range(m)]
ds={} # ds[(l,r)]:rがlのどれだけ右にいるか
dr={} # dr[i]:r=iのヒントのlの集合
import sys
sys.setrecursionlimit(10**7)
def add(l,r,d):
  if (r,l) in ds:
    print('No')
    exit()
  if (l,r) in ds and ds[(l,r)]!=d:
    print('No')
    #print(ds)
    exit()
  ds[(l,r)]=d
  if r in dr:
    dr[r].add(l)
  else:
    dr[r]=set([l])
  if l in dr:
    for i in dr[l]:
      add(i,r,ds[(i,l)]+d)

for l,r,d in lrd:
  add(l,r,d)

print('Yes')
#print(ds)


### FIXED CODE ###

n,m=map(int,input().split())
lrd=[list(map(int,input().split())) for _ in range(m)]
g=[[] for _ in range(n)]
for l,r,d in lrd:
  g[l-1].append([d,r-1])
  g[r-1].append([-d,l-1])

no_seen=set(range(n))
inf=float('inf')
dst=[inf]*n
while no_seen:
  todo=[[0,no_seen.pop()]]
  #print(todo)
  while todo:
    d,t=todo.pop()
    no_seen.discard(t)
    l=g[t]
    for di,ti in l:
      if dst[ti]!=inf and dst[ti]!=d+di:
        print('No')
        exit()
      elif dst[ti]!=inf and dst[ti]==d+di:
        pass
      else:
        todo.append([d+di,ti])
        dst[ti]=d+di

print('Yes')
### BUGGY CODE ###

N, Q = map(int, input().split())
s = input()
spells = []
for i in range(Q):
    spells.append(list(input().split()))
T = 0
D = 1

s_idx = {}
for i in range(N):
    if(s[i] in s_idx):
        s_idx[s[i]] += [i]
    else:
        s_idx[s[i]] = [i]
#print("s_idx={}".format(s_idx))

golems = [1] * N
g_num = N
for spl in spells:
#    print("spl={}, {}".format(spl, spl[T] in s_idx))
    if(True != (spl[T] in s_idx)):
#        print("skip")
        continue
    if("L" == spl[D]):
        for i in sorted(s_idx[spl[T]]):
            if(0 == i):
                g_num -= golems[i]
            else:
                golems[i - 1] += golems[i]
            golems[i] = 0
    elif("R" == spl[D]):
        for i in sorted(s_idx[spl[T]], reverse=True):
            if(N - 1 == i):
                g_num -= golems[i]
            else:
                golems[i + 1] += golems[i]
            golems[i] = 0

print(str(g_num))


### FIXED CODE ###

N, Q = map(int, input().split())
s = " " + input() + " "
td = []
for i in range(Q):
    td.append(input().split())
#print("td = {}".format(td))

llim = 0
rlim = N + 1
for t, d in reversed(td):
    if((s[llim + 1] == t) and ("L" == d)):
        llim += 1
    elif((s[llim] == t) and ("R" == d)):
        llim -= 1
    if((s[rlim - 1] == t) and ("R" == d)):
        rlim -= 1
    elif((s[rlim] == t) and ("L" == d)):
        rlim += 1
#    print("td = {}, llim = {}, rlim = {}".format([t, d], llim, rlim))

print(str(max(0, rlim - llim - 1)))
### BUGGY CODE ###

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

count = 0
for i in range(N):
    for j in range(i+1, N):
        if A[i] == A[j]:
            count = count + 1

if count == 0:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

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

A.sort()
count = 0

for i in range(1, N):
    if A[i-1] == A[i]:
        count += 1
        break

if count == 0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

def main():
	N, K = MAP()
	S = input()

	flg = [int(S[0])]
	count = []
	cnt = 1
	tmp = S[0]

	for x in S[1:]:
		if x == tmp:
			cnt += 1
		else:
			tmp = x
			flg.append(int(tmp))
			count.append(cnt)
			cnt = 1
	count.append(cnt)

	ans = 0
	for i in range(len(flg)):
		if flg[i]:
			ans = max(ans, sum(count[i:i+2*K+1]))
		else:
			ans = max(ans, sum(count[i:i+2*K]))

	print(ans)

if __name__ == '__main__':
	main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
#INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
S = [int(s) for s in input()] + [1]

r = -1
ans = 0
cnt = 0
used = [0]*(N+1)

for l in range(N):
	if S[l] + S[l-1] == 0:
		continue
	while r < N and used[r] - used[l-1] <= K:
		r += 1
		if S[r-1] == 1 and S[r] == 0:
			used[r] = used[r-1] + 1
		else:
			used[r] = used[r-1]
	ans = max(ans, r-l)

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

import fractions
import copy
from functools import reduce
N=int(input())
A=list(map(int,input().split()))
B=[]
c=0
def gcd(*n):
  return reduce(fractions.gcd, n)
for i in range(N):
  c=copy.deepcopy(A[i])
  A.pop(i)
  B.append(gcd(*A))
  A.insert(i,c)
  c=0
print(max(B))

### FIXED CODE ###

import fractions
N=int(input())
A=list(map(int,input().split()))
ans=0  #更新用
#端っこの処理用
l=[0]*(N+1)
r=[0]*(N+1)
for i in range(N):
  l[i+1]=(fractions.gcd(l[i],A[i]))
  r[N-i-1]=(fractions.gcd(r[N-i],A[N-1-i]))
for j in range(N):
  ans=max(ans,fractions.gcd(l[j],r[j+1]))
print(ans)
### BUGGY CODE ###

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

Q = int(input())
for j in range(Q):
    BC= list(input().split())
    A = [int(BC[1]) if i == int(BC[0]) else i for i in A]
    print(sum(A))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = sum(A)
C = Counter(A)

for i in range(Q):
    b, c = map(int, input().split())
    if C[b] != 0:
        cnt = C[b]
        C[c] += cnt
        C[b] = 0
        ans += (c-b) * cnt
    print(ans)
### BUGGY CODE ###

N, K = map(int,input().split())
h = list(map(int,input().split()))
inf = float('inf')
dp = [inf]*(N)
dp[0]=0
for i in range(1,N):
  for j in range(0,K+1):
    if 0<=i-j:
      dp[i]=min(dp[i],dp[i-j]+abs(h[i-j]-h[i]))
 
print(dp[-1])




### FIXED CODE ###

from numba import jit
import math

N, K = map(int,input().split())
h = list(map(int,input().split()))
@jit
def nya(N, K, h):
  dp=[0]*N
  for i in range(1,N):
    value=math.inf
    for j in range(1,K+1):
      if i-j<0:
        break
      value=min(value,dp[i-j]+abs(h[i]-h[i-j]))
    dp[i]=value
  return(dp[N-1])
 
print(nya(N,K,h))
### BUGGY CODE ###

def main():
    x = int(input())

    i = 1
    p = 0
    while True:
        if i == (x - p):
            print(i)
            break
        if i + 1 == (x - p):
            print(i + 1)
            break
        else:
            p += i
            i += 1


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    x = int(input())
    k = int(x ** .5)

    i = 0
    while True:
        p = i * (i + 1) // 2
        if p >= x:
            print(i)
            break
        i += 1


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

def mod_pow(a, n):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


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

mod = 10 ** 9 + 7

cnt = [0] * 60
for v in a:
    for i in range(60):
        if (v >> i) & 1:
            cnt[i] += 1

res = 0
for v in a:
    for i in range(60):
        if (v >> i) & 1:
            res = (res + (n - cnt[i]) * mod_pow(2, i) % mod) % mod
        else:
            res = (res + cnt[i] * mod_pow(2, i) % mod) % mod

print(res * mod_pow(2, mod - 2) % mod)

### FIXED CODE ###

def mod_pow(a, n):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


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

mod = 10 ** 9 + 7

cnt = [0] * 60
for v in a:
    for i in range(60):
        if (v >> i) & 1:
            cnt[i] += 1

pow_2 = [1]
for i in range(60):
    pow_2.append(pow_2[-1] * 2 % mod)

res = 0
for v in a:
    for i in range(60):
        if (v >> i) & 1:
            res = (res + (n - cnt[i]) * pow_2[i] % mod) % mod
        else:
            res = (res + cnt[i] * pow_2[i] % mod) % mod

print(res * mod_pow(2, mod - 2) % mod)
### BUGGY CODE ###

N = int(input())
S = input()
black = [s=="#" for s in S]
ans = N - sum(black)
if sum(black)==0:
    ans = 0
for i in range(N):
    a = sum(black[:i])
    b = N-i-sum(black[i:])
    ans = min(ans,a+b)
print(ans)

### FIXED CODE ###

from itertools import accumulate

N = int(input())
S = input()
black = [int(s=="#") for s in S]
white = [int(s==".") for s in S[::-1]]

a_black = [0]+list(accumulate(black))
a_white = list(accumulate(white))[::-1]+[0]

ans = 1000000
for b,w in zip(a_black,a_white):
    ans = min(ans, b+w)
print(ans)
### BUGGY CODE ###

S = input()
INF = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
index = 1
dp[0][0] = 1
for i in range(len(S)):
    c = S[-i - 1]
    if c == '?':
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j * index + k) % 13] += dp[i][k]
                dp[i + 1][(j * index + k) % 13] %= INF
    else:
        c = int(c)
        for k in range(13):
            dp[i + 1][(c * index + k) % 13] += dp[i][k]
            dp[i + 1][(c * index + k) % 13] %= INF
    index *= 10
    index %= 13

print(dp[len(S)][5])

### FIXED CODE ###

S = input()
INF = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
index = 1
dp[0][0] = 1
for i in range(len(S)):
    c = S[-i - 1]
    if c == '?':
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j * index + k) % 13] += dp[i][k]
                dp[i + 1][(j * index + k) % 13] %= INF
    else:
        c = int(c)
        for k in range(13):
            dp[i + 1][(c * index + k) % 13] += dp[i][k]
            dp[i + 1][(c * index + k) % 13] %= INF
    index *= 10
    index %= 13

print(dp[len(S)][5])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def main():
    N,M= map(int,input().split())
    List=[list(map(int,input().split())) for i in range(M)]
    ListN = list()
    List3 = list()
    for k in range(1,N+1):
        ListN.append(k)
    for i in range(M):
        List2 = list()
        x = List[i][0]
        y = List[i][1]
        for j in range(x,y+1):
            List2.append(j)
        for Li in List2:
            for Ln in ListN:
                if Li == Ln:
                    List2.append(Ln)
    List3 = list(set(List2))
    print(len(List3))

if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    N,M = map(int,input().split())
    L = []
    R = []
    for _ in range(M):
        l,r = map(int,input().split())
        L.append(l)
        R.append(r)
    L.sort(reverse=True)
    R.sort()
    lmax = L[0]
    rmin = R[0]
    print(max(0,rmin-lmax+1))



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

mod = 10**9 + 7
S = input()

dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] != '?':
        for m in range(13):
            dp[i+1][(10*m+int(S[i])) % 13] += dp[i][m]
            dp[i+1][(10*m+int(S[i])) % 13] %= mod
    else:
        for c in range(10):
            for m in range(13):
                dp[i+1][(10*m+c) % 13] += dp[i][m]
                dp[i+1][(10*m+c) % 13] %= mod

print(dp[len(S)][5])


### FIXED CODE ###

mod = 10**9+7
S = [int(x) if x != "?" else -1 for x in input()]

dp = [[0] * 13 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] == -1:
        for d in range(10):
            for j in range(13):
                dp[i+1][(j*10+d) % 13] += dp[i][j]
    else:
        d = S[i]
        for j in range(13):
            dp[i+1][(j*10+d) % 13] += dp[i][j]

    for k in range(13):
        dp[i+1][k] = dp[i+1][k] % mod

    # print(dp)

print(dp[len(S)][5])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
  n = int(input())
  xl = []
  ans = 0
  for i in range(n):
    xl.append(list(map(int, input().split())))
    xl.sort(key = lambda x:x[1])
    road = set()
  for i in range(n):
    sub = {}
    location = xl[i][0]
    arm = xl[i][1]
    sub = {j for j in range(max(0, location-arm+1), location+arm)}
    num_sub = len(sub)
    num_road = len(road)
    Z = road|sub
    if len(Z) ==num_sub + num_road:
      road = Z
      ans += 1

  print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
X = []
for i in range(n):
  x, l = map(int, input().split())
  X.append([x-l, x+l])
X.sort()
temp = X[0][1]
count = n
for i in range(1,n):
  if temp>X[i][0]:
    count -= 1
    temp = min(temp, X[i][1])
  else:
    temp = X[i][1]
print(count)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(N: int, P: int, S: str):
    ans = 0
    DP = [0]*P
    for i in range(N):
        c = int(S[i]) % P
        nDP = [0]*P
        nDP[c % P] += 1
        for p in range(P):
            nDP[(10*p + c) % P] += DP[p]
        DP = nDP
        ans += DP[0]
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: int, S: str):

    if P == 2 or P == 5:
        tot = 0
        for i, c in enumerate(S):
            c = int(c)
            if c % P == 0:
                tot += i+1
        print(tot)
        return

    U = [0]*(N+1)
    a = 0
    beki = 1
    for i in range(N-1, -1, -1):
        a += beki*int(S[i])
        a %= P
        U[i] = a
        beki = (beki * 10) % P
    table = [0]*P
    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


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

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())


N = int(input())
lines = []

for i in range(N):
	lines.append(inpl())

ans = 0
for s in range(N):
	for t in range(s+1,N):
		c = lines[s][t]
		ans += c
		for mid in range(N):
			if mid == s or mid == t:
				continue
			a = lines[s][mid]
			b = lines[mid][t]
			if a+b < c:
				print(-1)
				sys.exit()
			elif a+b == c:
				ans -= c
				break
print(ans)

### FIXED CODE ###

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())


N = int(input())
lines = []

for i in range(N):
	lines.append(inpl())

ans = 0
for s in range(N):
	for t in range(s+1,N):
		c = lines[s][t]
		ans += c
		for mid in range(N):
			if mid == s or mid == t:
				continue
			a = lines[s][mid]
			b = lines[mid][t]
			if a+b < c:
				print(-1)
				sys.exit()
			elif a+b == c:
				ans -= c
				break
print(ans)
### BUGGY CODE ###

import numpy as np
h,w=map(int,input().split())
c=np.array([list(input()) for _ in range(h)])

def lamp(isTrans):
    if isTrans:
        grid=np.transpose(c)
        memo=np.array([[0]*h]*w)
    else:
        grid=c
        memo=np.array([[0]*w]*h)

    H,W=grid.shape

    for i in range(H):
        seen=np.zeros(W, dtype=int)
        for j in range(W):
            if grid[i][j]=="#":
                continue
            if seen[j]:
                continue
            k=0
            while j+k<W:
                if grid[i][j+k]=="#":
                    break
                k+=1
            memo[i][j:j+k]=k
            seen[j:j+k]=1

    if isTrans:
        return np.transpose(memo)
    else:
        return memo

ans=lamp(1)+lamp(0)-1
print(ans.max())

### FIXED CODE ###

import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def calc(x, isTrans):
    if isTrans:
        y = np.copy(x.T)
    else:
        y = np.copy(x)

    for i in range(len(y)):
        xxx = np.copy(y[i])
        tmp_l = np.arange(len(xxx))
        tmp_l[xxx > 0] = 0
        np.maximum.accumulate(tmp_l, out=tmp_l)
        left = tmp_l

        xxx_reverse = xxx[::-1]
        tmp_r = np.arange(len(xxx_reverse))
        tmp_r[xxx_reverse > 0] = 0
        np.maximum.accumulate(tmp_r, out=tmp_r)
        right = len(xxx)-tmp_r[::-1]-1

        y[i] = right-left-1
        y[i][xxx == 0] = 0

    if isTrans:
        return np.transpose(y)
    else:
        return y


if __name__ == "__main__":
    h, w = map(int, readline().split())
    room = np.zeros((h+2, w+2), dtype=np.int)
    for i in range(1, h+1):
        room[i][1:-1] = [0 if i == "#" else 1 for i in input()]

    a = calc(room, True)
    b = calc(room, False)
    ans = (a + b).max() - 1
    print(ans)
### BUGGY CODE ###

n = int(input())
y = 0

def gcd(x, y):
  if x % y == 0:
    return y
  return int(gcd(y, x%y))

for i in range(n):
  for j in range(n):
    for k in range(n):
      i_ = i + 1
      j_ = j + 1
      k_ = k + 1
      y_ = gcd(gcd(i_, j_), k_)
      y += y_
 
print(y)

### FIXED CODE ###

import math
import numpy as np
import numba
import math

n = int(input())

@numba.jit
def main(n):
  lis = np.zeros((n, n, n))
  for i in range(n):
    for j in range(n):
      for k in range(n):
        lis[i][j][k] = math.gcd(math.gcd(i+1, j+1), k+1)
  return int(np.sum(lis))

print(main(n))
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()

import re
ptn = re.compile(r"AC")

for _  in range(Q):
  l, r = map(int,input().split())
  x = re.findall(ptn,S[l-1:r])
  print(len(x))

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
  t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)
for _ in range(Q):
  l, r = map(int,input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

n = int(input())

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

total = 0

for i in range(0,n-1):
    for x in range(i+1,n):
        seki = list1[i] * list1[x]
        total += seki

mod = 1000000007

kotae = total % mod

print(kotae)


### FIXED CODE ###

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

mod = 10 ** 9 + 7
total = 0
y = sum(list1)

for i in range(0,n-1):
    y = y- list1[i]
    total += list1[i] * y % mod

total = total % mod
print(total)