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

def makefac(n):
    global faclist
    faclist = [1, 1]
    for i in range(2, n + 1):
        faclist.append(faclist[-1] * i % MOD)
    return None
def mcomb(n, r):#nCr % MOD
    return faclist[n] * pow(faclist[r],MOD - 2, MOD) * pow(faclist[n-r], MOD - 2, MOD)
def mperm(n, r):#nPr % MOD
    return faclist[n] * pow(faclist[n-r],MOD - 2, MOD)

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
makefac(M)
ans = mperm(M, N)
for k in range(1, N + 1):
    ans += ((-1)**k * mcomb(N, k) * mperm(M - k, N - k)) % MOD
ans = ans * mperm(M, N) % MOD
print(ans)


### FIXED CODE ###

def makefac(n):
    global faclist
    faclist = [1, 1]
    for i in range(2, n + 1):
        faclist.append(faclist[-1] * i % MOD)
    return None
def mcomb(n, r):#nCr % MOD
    return faclist[n] * pow(faclist[r],MOD - 2, MOD) * pow(faclist[n-r], MOD - 2, MOD)
def mperm(n, r):#nPr % MOD
    return faclist[n] * pow(faclist[n-r],MOD - 2, MOD)

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
makefac(M)
ans = mperm(M, N)
for k in range(1, N + 1):
    ans += ((-1)**k * mcomb(N, k) * mperm(M - k, N - k)) % MOD
ans = ans * mperm(M, N) % MOD
print(ans)
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    for x,l,r in sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        while l<r:
            if r&1:
                r-=1
                data[r-1]=x
            if l&1:
                data[l-1]=x
                l+=1
            l>>=1
            r>>=1
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

K = int(input())

def gcd(n,m):
    if n < m :
        n , m = m , n
    while n % m != 0 :
        n , m = m , n % m
    
    return m
  
S = 0


for a in range (1, K + 1):
    for b in range (1, K + 1):
        for c in range (1, K + 1):
            d = gcd(a,b)
            S += gcd(c,d)

print ( S )
    


### FIXED CODE ###

K = int(input())

def gcd(n,m,l):
    if n < m :
        n , m = m , n
    while n % m != 0 :
        n , m = m , n % m
    
    if m < l :
        m , l = l , m
    while m % l != 0 :
        m , l = l , m % l
    
    return l
  
S = 0

for a in range (1, K + 1):
    for b in range (1, K + 1):
        for c in range (1, K + 1):
            S += gcd(a, b, c)

print ( S )
### BUGGY CODE ###

n,m = list(map(int,input().split()))
for i in range(m):
    l,r=list(map(int,input().split()))
    if i == 0:
        ans = set(range(l,r+1))
    else:
        ans = ans & set(range(l,r+1))
print(len(ans))


### FIXED CODE ###

n,m = list(map(int,input().split()))
la = 0
ra = n
for i in range(m):
    l,r=list(map(int,input().split()))
    la = max(la,l)
    ra = min(ra,r)
print(max(0,ra-la+1))
### BUGGY CODE ###

n,m=map(int,input().split())
field=[[] for i in range(3*n)]
for i in range(m):
     x,y=map(int,input().split())
     x,y=x-1,y-1
     field[3*x].append(3*y+1)
     field[3*x+1].append(3*y+2)
     field[3*x+2].append(3*y)

s,t=map(int,input().split())
s,t=s-1,t-1
s,t=3*s,3*t

que=[s]
ok=[s]
cnt=0
flag=0
while que!=[]:
     que2=[]
     cnt+=1
     for i in que:
          for j in field[i]:
               if j not in ok:
                    ok.append(j)
                    if j==t:
                         print(cnt//3)
                         flag=1
                         break
                    que2.append(j)
     que=que2
if flag==0:
     print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
     n,m=map(int,input().split())
     field=[[] for i in range(3*n)]
     for i in range(m):
          x,y=map(int,input().split())
          x,y=x-1,y-1
          field[3*x].append(3*y+1)
          field[3*x+1].append(3*y+2)
          field[3*x+2].append(3*y)
     
     s,t=map(int,input().split())
     s,t=s-1,t-1
     s,t=3*s,3*t
     
     d=[float('inf') for i in range(3*n)]
     d[s]=0
     
     que=[s]
     cnt=0
     while que!=[]:
          que2=[]
          cnt+=1
          for i in que:
               for j in field[i]:
                    if d[j]>cnt:
                         d[j]=cnt
                         que2.append(j)
          que=que2
     if d[t]==float('inf'):
          print(-1)
     else:
          print(d[t]//3)
     return 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

class BIT():
	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def getsum(self, k):
		ret = 0
		while k:
			ret += self.bit[k]
			k -= k & -k
		return ret

	def p_sum(self, i, j):
		return self.getsum(j) - self.getsum(i - 1)

	def add(self, k, x):
		while k <= self.n:
			self.bit[k] += x
			k += k & -k

	def bisect(self, x):
		i, m = 0, 1 << (self.n.bit_length() - 1)
		while m:
			t = i + m
			if t < self.n and self.bit[t] < x:
				i = t
				x -= self.bit[i]
			m //= 2
		return i + 1

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter as get
n,q=map(int,input().split())
event=[]
Xs=[]
for _ in range(n):
	s,t,x=map(int,input().split())
	event.append((-2,s-x,x))
	event.append((-1,t-x,x))
	Xs.append(x)
Xs.sort()
for _ in range(q):
	d=int(input())
	event.append((0,d,None))
event.sort(key=get(1))
x_to_i={x:i for i,x in enumerate(Xs)}
bit=BIT(n+1)
Xs.append(-1)
bit.add(n,1)
ans=[]
for flg,time,x in event:
	if flg==-2:
		bit.add(x_to_i[x],1)
	elif flg==-1:
		bit.add(x_to_i[x],-1)
	else:
		i=bit.bisect(1)
		ans.append(Xs[i])
print("\n".join(map(str,ans)))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter as get
from heapq import *


def main():
	n, q = map(int, input().split())
	event = []
	Xs = []
	for _ in range(n):
		s, t, x = map(int, input().split())
		event.append((-2, s - x, x))
		event.append((-1, t - x, x))
		Xs.append(x)
	for _ in range(q):
		d = int(input())
		event.append((0, d, None))
	event.sort(key=get(1))
	active = {x: 0 for x in Xs}
	candidate = []
	ans = []
	for flg, time, x in event:
		if flg == -2:
			active[x] = 1
			heappush(candidate, x)
		elif flg == -1:
			active[x] = 0
		else:
			res = -1
			while candidate:
				c = heappop(candidate)
				if active[c]:
					heappush(candidate, c)
					res = c
					break
			ans.append(res)
	print("\n".join(map(str, ans)))


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

n,K=map(int,input().split())
lists=[]
for i in range(n):
    x,y=map(int,input().split())
    lists.append((x,y))
anslist=[]
for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            for l in range(k+1,n):       
                a=lists[i][0]
                b=lists[j][0]
                c=lists[k][1]
                d=lists[l][1]
                counter=0
                for s in range(n):
                    p,q=lists[s][0],lists[s][1]
                    if min(a,b)<=p<=max(a,b) and min(d,c)<=q<=max(c,d):
                        counter+=1
                    if counter>=K:
                        anslist.append(abs(a-b)*abs(c-d))
print(min(anslist))        

### FIXED CODE ###

#atcoder -take a rest-(easy)

def main():
    N,K = map(int,input().split())
    que = []
    que_x =  []
    que_y = []
    for i in range(N):
        x,y = map(int,input().split())
        que_x.append(x)
        que_y.append(y)
        que.append((x,y))
    que_x.sort()
    que_y.sort()
    ans = 10**100
    for i in range(N):
        for j in range(i,N):
            for _i in range(N):
                for _j in range(_i,N):
                    h,w = que_x[j]-que_x[i],que_y[_j] -que_y[_i]
                    cnt = 0
                    for x,y in que:
                        if que_x[i]<=x<=que_x[j] and que_y[_i]<=y<=que_y[_j]:
                            cnt += 1
                    if cnt >=K:
                        ans = min(ans,h*w)
    print(ans)
    return




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

import itertools
import heapq
import sys
import functools
import operator
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = [list(i) for i in comb]
  
A = [functools.reduce(operator.mul,l[i]) for i in range(len(l))]

l_max = max(A)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###


n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
p = map(lambda x: sum(range(1,x+1))/x, p)

l = [0]
for i,v in enumerate(p):
    prev = l.pop()
    l.append(prev)
    l.append(prev + v)

ans = 0
for i in range(k, len(l)):
    tmp = l[i] - l[i-k]
    if ans < tmp:
        ans = tmp

print(ans)

### FIXED CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
p = map(lambda x: sum(range(1,x+1))/x, p)
 
l = [0]
for i,v in enumerate(p):
    prev = l.pop()
    l.append(prev)
    l.append(prev + v)
 
ans = 0
for i in range(k, len(l)):
    tmp = l[i] - l[i-k]
    if ans < tmp:
        ans = tmp
 
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = -10 ** 9
    # 全ての点を始点とした場合を考える(N通り)
    for start in range(N):
        # 始点を含むループを探す，スコアの累積和も勘定しておく
        now = start
        loop = []
        total = 0
        while now != start or not loop:
            loop.append(C[now])
            now = P[now]
            total += C[now]
        # ループごとの最大スコアを探す
        length = len(loop)
        t = 0
        for i in range(length):
            t += loop[i]
            # ループ長 > Kなら，ループ途中で探索終了
            if i + 1 > K:
                break
            # ループ長 <= Kなら，ループを周回するので
            # それを利用して探索を省略
            now = t
            if total > 0:
                e = (K - (i + 1)) // length
                now += total * e
            ans = max(ans, now)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = -10 ** 9
    for start in range(N):
        # ループを探す
        now = start
        loop = []
        total = 0
        while now != start or not loop:
            loop.append(C[now])
            now = P[now]
            total += C[now]
        # ループごとの最大スコアを探す
        length = len(loop)
        # sum_loop = sum(loop)
        # # ループ長よりも操作回数が多いか？，ループを周回すると得か？で場合分け
        # res = 0 if sum_loop <= 0 else sum_loop * (K // length)
        # limit = K if K <= length else K % length
        # for k in range(limit):
        #     res += loop[k]
        #     ans = max(ans, res)
        t = 0
        for i in range(length):
            t += loop[i]
            if i + 1 > K:
                break
            now = t
            if total > 0:
                e = (K - (i + 1)) // length
                now += total * e
            ans = max(ans, now)
    print(ans)


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

import sys
n = int(input())
a = []
for i in range(n):
    k = [int(x) for x in input().split()]
    j = []
    for i in range(1, len(k)+1):
        j.append(k[-i])
    a.append(j)
ans = 0
while a:
    s = 1
    todaylist = []
    for i in range(n):
        if i+1 in todaylist:
            continue
        if a[i]:
            if a[i][-1] in todaylist:
                continue
            b = a[i][-1]-1
            if a[b]:
                if a[b][-1] == i+1:
                    a[i].pop()
                    a[b].pop()
                    todaylist.append(i+1)
                    todaylist.append(b+1)
                    s = 0
    ans += 1
    if s:
        print(-1)
        sys.exit()
    if not any(a):
        break
print(ans)

### FIXED CODE ###

import sys
from copy import deepcopy as copy

def main():
    input = sys.stdin.readline
    n = int(input())
    a = [None]*n
    for i in range(n):
        a[i] = [int(x)-1 for x in input().split()]
    
    index = [0]*n
    search = [int(x) for x in range(n)]
    ans = 0
    while True:
        already = set()
        judge = True
        sub = []
        for key in search:
            if index[key] == n-1:
                continue
            key2 = a[key][index[key]]
            if index[key2] == n-1:
                continue
            if key != a[key2][index[key2]]:
                continue
            if key in already or key2 in already:
                continue
            already.add(key)
            already.add(key2)
            index[key] += 1
            index[key2] += 1
            sub.append(key)
            sub.append(key2)
            judge = False
        if judge:
            break
        ans += 1
        search = copy(sub)
        
    for value in index:
        if value != n-1:
            print(-1)
            sys.exit()
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

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


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

n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc=[tuple(map(int,input().split())) for _ in range(q)]
d={}
for ai in a:
    if ai not in d:
        d[ai]=0
    d[ai]+=1
# print(d)
for bi,ci in bc:
    if bi in d:
        tmp=d[bi]
        d[bi]=0
        if ci not in d:
            d[ci]=0
        d[ci]+=tmp
    ans=0
    for key in d:
        ans+=key*d[key]
    print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc=[tuple(map(int,input().split())) for _ in range(q)]
d={}
for ai in a:
    if ai not in d:
        d[ai]=0
    d[ai]+=1
# print(d)

ans=0
for key in d:
    ans+=key*d[key]

for bi,ci in bc:
    if bi in d:
        tmp=d[bi]
        d[bi]=0
        ans-=bi*tmp
        if ci not in d:
            d[ci]=0
        d[ci]+=tmp
        ans+=ci*tmp
    print(ans)
### BUGGY CODE ###

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

import bisect
a.sort()
b.sort()
c.sort()
ans = 0
for A in a:
    key_b = bisect.bisect_left(b,A+1)
    if key_b == len(b):
        continue
    for i in range(key_b,len(b)):
        key_c = bisect.bisect_left(c,b[i]+1)
        ans += len(c) - key_c
print(ans)

### FIXED CODE ###

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

import bisect
a.sort()
b.sort()
c.sort()
ans = 0
for i in range(len(b)):
    ab = bisect.bisect_right(a,b[i]-1) # b[i]より真に小さいaの要素数
    bc = len(c) - bisect.bisect_left(c,b[i]+1) # b[i]より真に大きいcの要素数
    ans += ab*bc
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
operation = [list(map(int, input().split())) for _ in range(q)]

from  collections import Counter

dict_a = Counter(a)

for i in range(q):
  dict_a[operation[i][1]] += dict_a[operation[i][0]]
  dict_a[operation[i][0]] = 0
  s = 0
  for (k, v) in dict_a.items():
    s += k*v
  print(s)


### FIXED CODE ###

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

from  collections import Counter

dict_a = Counter(a)
s = sum(a)

for i in range(q):
  b, c = map(int, input().split())
  s -= b*dict_a[b]
  s += c*dict_a[b]
  dict_a[c] += dict_a[b]
  dict_a[b] = 0
  print(s)
### BUGGY CODE ###

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

for _ in range(Q):
    A.append(int(input()))

for n in range(N):
    freq = A.count(n + 1)
    if K- Q + freq <= 0:
        print('No')
    else:
        print('Yes')





### FIXED CODE ###

N, K, Q = map(int, input().split())
index_list = [int(input()) - 1 for i in range(Q)]

zero_list = [0 for n in range(N)]

ori = K - Q
for i in range(Q):
    zero_list[index_list[i]] += 1
for i in range(N):
    zero_list[i] += ori
for i in range(N):
    if zero_list[i] > 0:
        print('Yes')
    else:
        print('No')

# shakayamiさんのコードを参考にしました
# for文が入れ子になると遅くなるから，出来るだけそうしない
### BUGGY CODE ###

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
weight=[items[i][0] for i in range(n)]
value=[items[i][1] for i in range(n)]

limit=sum(value)
inf=10**9
dp=[[0]+[inf]*limit for i in range(n+1)]
#print(dp)
for i in range(n):
  w=weight[i]
  v=value[i]
  for j in range(limit+1):
    if j>=v:
      dp[i+1][j]=min(dp[i][j],dp[i][j-v]+w)
    else:
      dp[i+1][j]=min(dp[i][j],w)
#print(dp[n])
ans=max([i for i in range(limit+1) if dp[n][i]<=W])
print(ans)

### FIXED CODE ###

n,W=map(int,input().split())
items=[list(map(int,input().split())) for i in range(n)]
weight=[items[i][0] for i in range(n)]
value=[items[i][1] for i in range(n)]

limit=sum(value)
inf=10**9
dp=[[0]+[inf]*limit for i in range(n+1)]
#print(dp)
for i in range(n):
  w=weight[i]
  v=value[i]
  for j in range(limit+1):
    if j>=v:
      dp[i+1][j]=min(dp[i][j],dp[i][j-v]+w)
    else:
      dp[i+1][j]=min(dp[i][j],w)
#print(dp[n])
ans=max([i for i in range(limit+1) if dp[n][i]<=W])
print(ans)
### BUGGY CODE ###

def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    L = [[0] * w for _ in range(h)]
    R = [[0] * w for _ in range(h)]
    U = [[0] * w for _ in range(h)]
    D = [[0] * w for _ in range(h)]
    ans = 0
    for i in range(h):
        for j in range(w):
            if j != 0:
                L[i][j] = L[i][j - 1]
            if s[i][j] == ".":
                L[i][j] += 1
            else:
                L[i][j] = 0
    for i in range(h):
        for j in range(w - 1, -1, -1):
            if j != w - 1:
                R[i][j] = R[i][j + 1]
            if s[i][j] == ".":
                R[i][j] += 1
            else:
                R[i][j] = 0
    for j in range(w):
        for i in range(h):
            if i != 0:
                U[i][j] = U[i - 1][j]
            if s[i][j] == ".":
                U[i][j] += 1
            else:
                U[i][j] = 0
    for j in range(w):
        for i in range(h - 1, -1, -1):
            if i != h - 1:
                D[i][j] = D[i + 1][j]
            if s[i][j] == ".":
                D[i][j] += 1
            else:
                D[i][j] = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
L = [[0] * w for _ in range(h)]
R = [[0] * w for _ in range(h)]
U = [[0] * w for _ in range(h)]
D = [[0] * w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if j != 0:
            L[i][j] = L[i][j - 1]
        if s[i][j] == ".":
            L[i][j] += 1
        else:
            L[i][j] = 0
for i in range(h):
    for j in range(w - 1, -1, -1):
        if j != w - 1:
            R[i][j] = R[i][j + 1]
        if s[i][j] == ".":
            R[i][j] += 1
        else:
            R[i][j] = 0
for j in range(w):
    for i in range(h):
        if i != 0:
            U[i][j] = U[i - 1][j]
        if s[i][j] == ".":
            U[i][j] += 1
        else:
            U[i][j] = 0
for j in range(w):
    for i in range(h - 1, -1, -1):
        if i != h - 1:
            D[i][j] = D[i + 1][j]
        if s[i][j] == ".":
            D[i][j] += 1
        else:
            D[i][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print(ans)
### BUGGY CODE ###


n = int(input())
p = list(map(int,input().split()))
ans = 1
l = []

for i in range(1,n):
    l = p[0:i]
    if p[i] <= min(l):
        ans += 1
    else:
        pass

print(ans)


### FIXED CODE ###


n = int(input())
p = list(map(int,input().split()))
ans = 0
currentMin = 10 ** 9
s = []

for i in range(n):
    if currentMin > min(currentMin,p[i]):
        currentMin = min(currentMin,p[i])
        s.append(currentMin)
    else:
        s.append(currentMin)

for i in range(len(p)):
    if p[i] == s[i]:
        ans += 1

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

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

mod = 10**9+7



ans = 0
q2 = 1
for j in range(60):
    mm1 = 0
    for i in range(n):
        if a[i]>>j&1:
            mm1 += 1

    ttl = ((n-mm1)*mm1)
    ans += ((q2)*((ttl)%mod))%mod
    ans %= mod
    q2 = (q2*2)%mod

print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
 
mod = 10**9+7
 
 
 
ans = 0
q2 = 1
for j in range(60):
    mm1 = 0
    for i in range(n):
        if a[i]>>j&1:
            mm1 += 1
 
    ttl = ((n-mm1)*mm1)
    ans += ((q2)*((ttl)%mod))%mod
    ans %= mod
    q2 = (q2*2)%mod
 
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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