Harryxun/stf_run huggingface dataset:
import math
import os
import random
import re
import sys
def findpath(a):
  if len(a)==3:
    return min(abs(a[2]-a[1])+abs(a[1]-a[0]),abs(a[2]-a[0]))
  return min(abs(a[2]-a[0])+findpath(a[2::]),abs(a[1]-a[0])+findpath(a[1::]))
n=int(input())
a=input().split()
for i in range(n):
  a[i]=int(a[i])
print findpath(a)

### FIXED CODE ###

import math
import os
import random
import re
import sys
def dpfindpath(a):
	dpath=[int(0) for _ in range(len(a))]
	dpath[0]=0
	dpath[1]=abs(a[1]-a[0])
	for i in range(2,len(a)):
		dpath[i]=min(abs(a[i]-a[i-1])+dpath[i-1],abs(a[i]-a[i-2])+dpath[i-2])
	return dpath[len(a)-1]
n=int(input())
a=input().split()
for i in range(n):
  a[i]=int(a[i])
print (dpfindpath(a))
n = int(input())
s = input()

def trim(n, s):
    i = 0
    while i < n and s[i] == '.':
        i += 1
    start = i

    i = n
    while i > 0 and s[i - 1] == '#':
        i -= 1
    end = i

    return s[start:end]


def f(n, s):
    bs = 0
    ws = 0

    for c in s:
        if c == '#':
            bs += 1
        else:
            ws += 1
    return min(ws, bs)


def g(n, s):
    bs = 0
    ws = 0
    i = 0
    while i < n:
        if s[i] == '#':
            bs += 1
        else:
            break
        i += 1

    i = len(s)
    while i > 0:
        if s[i - 1] == '.':
            ws += 1
        else:
            break
        i -= 1

    return bs + ws

s = trim(n, s)
print(min(f(n, s), g(n, s)))


### FIXED CODE ###

n = int(input())
s = input()

a = [(0, 0) for _ in range(len(s) + 1)]

i = 0
while i < len(s):
    bs, ws = a[i + 1]
    b0, w0 = a[i]

    if s[i] == '#':
        bs += 1
    else:
        ws += 1

    a[i + 1] = (bs + b0, ws + w0)
    i += 1


i = 0
can = len(s)
while i < len(a):
    can = min(can, a[i][0] + a[-1][1] - a[i][1])
    i += 1

print(can)
#-*- encoding=utf-8 -*-

import numpy as np
import matplotlib.pyplot as plt
import sys

printf = sys.stdout.write


mat = []
new_map = []

r,c = map(int, raw_input().split())
for i in range(r):
    mat = map(int, raw_input().split())
    new_map.append(mat)


for i in range(r):
    new_map[i].append(sum(new_map[i][:]))
    for j in range(c):
        print new_map[i][j],
    printf(" " + str(new_map[i][j + 1]) + "\n")


for j in range(c + 1):
    a = 0
    for i in range(r):
        a += new_map[i][j]
    if j == c:
        printf(" " + str(a) + "\n")
        break
    else:
        print a,

### FIXED CODE ###

import sys

printf = sys.stdout.write


mat = []
new_map = []

r,c = map(int, raw_input().split())
for i in range(r):
    mat = map(int, raw_input().split())
    new_map.append(mat)


for i in range(r):
    new_map[i].append(sum(new_map[i][:]))
    for j in range(c):
        print new_map[i][j],
    printf(" " + str(new_map[i][j + 1]) + "\n")


for j in range(c + 1):
    a = 0
    for i in range(r):
        a += new_map[i][j]
    if j == c:
        printf(" " + str(a) + "\n")
        break
    else:
        print a,
import sys

s = a + input()

for i in range(3,len(s)):
  if s[i] != s[i-1] and s[i] != s[i-2]:
    continue
  elif s[i] == s[i-1]:
    print(i-1,i)
    sys.exit(0)
  elif s[i] == s[i-2]:
    print(i-2,i)
    sys.exit(0)
    
print(-1,-1)

### FIXED CODE ###

import sys

s = 'a' + input()

for i in range(3,len(s)):
  if s[i] != s[i-1] and s[i] != s[i-2]:
    continue
  elif s[i] == s[i-1]:
    print(i-1,i)
    sys.exit(0)
  elif s[i] == s[i-2]:
    print(i-2,i)
    sys.exit(0)

if s[1] == s[2]:
  print(1,2)
  sys.exit(0)
print(-1,-1)
N = int(input())
H = list(map(int, input().split()))

# ans = 1
# for i in range(1, N-1, 1):
#     #print((H[i] - H[i+1]))
#     if ((H[i-1] - H[i]) == 1) & ((H[i] - H[i+1]) == 0):
#         continue
#     elif ((H[i-1] - H[i]) <= 0) & ((H[i] - H[i+1]) <= 0):
#         continue
#     elif ((H[i-1] - H[i]) == -1) & ((H[i] - H[i+1]) == 1):
#         continue
#     else:
#         print('No')
#         ans = -1
#         break

#if (ans == 1): print('Yes')

ans = 1
for i in range(1, N-1, 1):
    #print((H[i] - H[i+1]))
    #print(i)
    if ((H[i-1] - H[i]) >= 1) & ((H[i] - H[i+1]) >= 1):
        print('No')
        ans = -1
        break
    elif ((H[i-1] - H[i]) == 0) & ((H[i] - H[i+1]) == 1):
        print('No')
        ans = -1
        break
    elif ((H[i-1] - H[i]) >= 2):
        print('No')
        ans = -1
        break
    elif ((H[i] - H[i+1]) >= 2):
        print('No')
        ans = -1
        break
    else:
        continue

if (H[0] - H[1] >= 2):
    print('No')
    ans = -1

if (ans == 1): print('Yes')

### FIXED CODE ###

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

ans = 1
for i in reversed(range(1, N, 1)):
    if (H[i-1] - H[i]) == 1:
        H[i-1] -= 1
    if (H[i-1] - H[i]) > 1:
        print('No')
        ans = -1
        break
if ans == 1: print('Yes')
N, M = map(int, input().split(" "))
stores = dict()
p = 10000000000

for i in range(N):
    if 1 in stores and stores[1] >= M:
      break
    Ai, Bi = map(int, input().split(" "))
    if Ai in stores:
        stores[Ai] += Bi
    else:
        stores[Ai] = Bi
    p = min(p, Ai)


price = 0
while True:
    if p in stores:
        if M <= stores[p]:
            price += p * M
            break
        else:
            price += p * stores[p]
            M -= stores[p]
    p += 1
print(price)


### FIXED CODE ###

H, W = map(int, input().split(" "))
h, w = map(int, input().split(" "))
print((H - h)*(W - w))
N = int(input())

a = list(map(int, input().split()))
ans = 1
for i in range(N):
    if a.index(0):
        ans = 0
        break
    ans = ans * a[i]
    if ans > 10**18:
        ans = -1
        break
print(ans)

### FIXED CODE ###

N = int(input())

a = list(map(int, input().split()))
ans = 1
if 0 in a:
    ans = 0
else :
    for i in range(N):
        ans = ans * a[i]
        if ans > 10**18:
            ans = -1
            break
print(ans)
def ppc(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

def sol():
    n=int(input())
    x=input()
    chk=0
    for i,j in enumerate(x[::-1]):
        if j=="1":
            chk+=2**i
    c,d={},{}
    ans=[]
    for i,j in enumerate(x[::-1]):
        p=pow(2,i)
        if j=="1":
            t=chk-p
        else:
            t=chk+p
        s=t
        cnt=0
        while t:
            if t not in c:
                pc=ppc(t)
                c[t]=pc
            else:
                pc=c[t]
            t%=pc
            cnt+=1
            if t in d:
                cnt+=d[t]
                break
        if s not in d:
            d[s]=cnt
        ans.append(cnt)
    for i in ans[::-1]:
        print(i)

if __name__=="__main__":
    sol()

### FIXED CODE ###

n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0)
    exit()
elif b==1:
    for i in range(n):
        if i==n-1: print(2)
        elif x[i]=="0": print(1)
        else: print(0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans,f=0,1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """2 3 1
3 3
3 3 3
1 2 1"""
        output = """5"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1 1 2
10
10
1 1 5
1 1 10"""
        output = """10"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """2 2 1
3 5
3 5
2 2 2"""
        output = """6"""
        self.assertIO(input, output)

if __name__ == "__main__":
    unittest.main()

### FIXED CODE ###

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

def resolve():
    a,b,m=map(int, input().split())
    la=list(map(int,input().split()))
    lb=list(map(int,input().split()))
    lm=[list(map(int,input().split())) for i in range(m)]
    nowari=min(la)+min(lb)
    warians=10**10
    for i in range(m):
        wari=la[(lm[i][0])-1]+lb[(lm[i][1])-1]-lm[i][2]
        if wari<warians:
            warians=wari
    print(min(nowari,warians))
resolve()
n = int(input())
A = list(map(int, input().sprit()))
for i in range(1,n):
  print(A.count(i))

### FIXED CODE ###

import collections

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

c = collections.Counter(A)

for i in range(1,n+1):
  print(c[i])
n = int(input())
l = list(map(int,input().split()))
a = 10**9
ans = 0
if l[i] <= a:
    ans += 1
    a = l[i]
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
a = 10**9
ans = 0
for i in range(n):
    if p[i]<=a:
        ans+= 1
        a = p[i]
print(ans)
def solve() :
    n = int(input()) 
    a = list(map(int, input().split()))

    total = 1

    if 0 in a :
        print(0)
        return

    for i in a :
        total *= i

        if total > 10 ** 18 :
            print(-1)
            return

    print(total)

if __name__ == "__main__" :
    solve()

### FIXED CODE ###

a, b = map(int, input().split())
print(a*b)
# coding: utf-8
# Here your code



N = int(input())
a = [int(i) for i in input().split()] 

result_1 = 0
before_sum =a[0]
after_sum =a[0]

for i in range(1,N):
    before_sum = after_sum
    after_sum = before_sum + a[i]
    if before_sum * after_sum > 0:
        if after_sum < 0:
            result_1 += 1 - after_sum
            after_sum = 1
        elif after_sum > 0:
            result_1 += 1 + after_sum
            after_sum = -1
    elif before_sum * after_sum == 0:
        result_1 += 1
        if before_sum < 0:
            after_sum = 1
        else:
            after_sum = -1

before_sum =int(-a[0]/abs(a[0]))
after_sum =before_sum
result_2 = 1 + abs(before_sum)


for i in range(1,N):
    before_sum = after_sum
    after_sum = before_sum + a[i]
    if before_sum * after_sum > 0:
        if after_sum < 0:
            result_2 += 1 - after_sum
            after_sum = 1
        elif after_sum > 0:
            result_2 += 1 + after_sum
            after_sum = -1
    elif before_sum * after_sum == 0:
        result_2 += 1
        if before_sum < 0:
            after_sum = 1
        else:
            after_sum = -1


print(min(result_1,result_2))


### FIXED CODE ###

# coding: utf-8
# Here your code

N = int(input())
a = [int(i) for i in input().split()] 

result_1 = 0
before_sum = a[0]

if a[0] <= 0:
    before_sum = 1
    result_1 += 1 + abs(a[0])

after_sum = before_sum

for i in range(1,N):
    before_sum = after_sum
    after_sum = before_sum + a[i]
    if i % 2 == 0:
        if after_sum <= 0:
            result_1 += 1 + abs(after_sum)
            after_sum = 1
    else:
        if after_sum >= 0:
            result_1 += 1 + abs(after_sum)
            after_sum = -1

result_2 = 0
before_sum = a[0]

if a[0] >= 0:
    before_sum = -1
    result_2 += 1 + abs(a[0])

after_sum = before_sum

for i in range(1,N):
    before_sum = after_sum
    after_sum = before_sum + a[i]
    if i % 2 == 1:
        if after_sum <= 0:
            result_2 += 1 + abs(after_sum)
            after_sum = 1
    else:
        if after_sum >= 0:
            result_2 += 1 + abs(after_sum)
            after_sum = -1

print(min(result_1,result_2))
S=str(input())
if S[0]==S[1] and S[2]==S[3]:
  print('Yes')
else if S[0]==S[2] and S[1]==S[3]:
  print('Yes')
else if S[0]==S[3] and S[1]==S[2]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

S=str(input())
if S[0]==S[1] and S[1]==S[2] and S[2]==S[3]:
  print('No')
elif S[0]==S[1] and S[2]==S[3]:
  print('Yes')
elif S[0]==S[2] and S[1]==S[3]:
  print('Yes')
elif S[0]==S[3] and S[1]==S[2]:
  print('Yes')
else:
  print('No')
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
      
    def group_count(self):
        return len(self.roots)

n, m = map(int, input().split())
un = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    un.union(a, b)
print(un.group_count() - 1)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
      
    def group_count(self):
        return len(self.roots())

n, m = map(int, input().split())
un = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    un.union(a, b)
print(un.group_count() - 1)
from functools import reduce
from operator import add
n=int(input())
v=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
print(reduce(add,[v[i]-c[i] for i in range(n) if v[i]>c[i]]))

### FIXED CODE ###

n=int(input())
v=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
dif=[]
for i in range(n):
  if v[i]>c[i]:
    dif.append(v[i]-c[i])
print(sum(dif))
import sys

def parent(i):
    return (i + 1) / 2 - 1

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def sibling(i):
    if i % 2 == 0:
        return i - 1
    else:
        return i + 1

def insert(S, k):
    S.append(k)
    idx = len(S) - 1
    while True:
        p = parent(idx)
        if p < 0 or S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p
    #print S

def extract(S):
    print S[0]
    S[0] = S[-1]
    S.pop()
    size = len(S)

    idx = 0
    while True:
        l, r = left(idx), right(idx)
        if l < size and S[idx] < S[l] and (r < size and S[r] <= S[l] or r >= size:
            S[idx], S[l] = S[l], S[idx]
            idx = l
        elif r < size and S[idx] < S[r]:
            S[idx], S[r] = S[r], S[idx]
            idx = r
        else:
            break
    #print S

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)

### FIXED CODE ###

import sys

def insert(k):
    global S, last
    S[last] = k
    idx = last
    while True:
        p = (idx + 1) / 2 - 1
        if S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p
    last += 1

def maxHeapify(i):
    global S, last
    l = 2 * i + 1
    r = 2 * i + 2

    if l < last and S[l] > S[i]:
        largest = l
    else:
        largest = i

    if r < last and S[r] > S[largest]:
        largest = r

    if largest != i:
        S[i], S[largest] = S[largest], S[i]
        maxHeapify(largest)

def extract():
    global S, last
    print S[0]
    last -= 1
    S[0], S[last] = S[last], 0
    maxHeapify(0)

lines = sys.stdin.readlines()
lines.pop()

S = [0] * 2000001
S[2000000] = 2000000000
last = 0
for line in lines:
    if line[0] == "i":
        insert(int(line[7:]))
    else:
        extract()
# 解答ちらっと見た
# 問題のキモは Cx,Cy,Hがそれぞれ100通り、
# 全探索をCx,Cy,Hに対して試みると 入力された情報のcheckを入れて101*101*100*100でTLEする。
# でもよく考えてみると、Cx,CyがわかればHはそのあとで出せるので Cx,Cyに対して全探索をする(101*101*100+100の計算量で済む)


def check(x, y, h, cx, cy):
    return h + abs(x - cx) + abs(y - cy)


def checks(x, y, eh, cx, cy, h):
    cah = max(h - abs(x - cx) - abs(y - cy), 0)
    return cah == eh


N = int(input())
H = {}

checkers = [(list(map(int, input().split()))) for _ in range(N)]
for x,y,h in checkers:
    if h>0:
        lockx=x
        locky=y
        lockh=h

for icx in range(101):
    for icy in range(101):
        H = set({})
        for checker in checkers:
            H.add(lockh + abs(lockx - icx) + abs(locky - icy))

        if len(H) == 1:
            # print('{} {} {}'.format(icx, icy, H[0]))
            ok = True
            for c in checkers:
                if not checks(c[0], c[1], c[2], icx, icy, H[0]):
                    # print('failedin {} {} {} {} {} {}'.format(c[0], c[1], c[2], icx, icy, H[0]))
                    ok = False
                    break
            if ok:
                print('{} {} {}'.format(icx, icy, H[0]))
                exit(0)


### FIXED CODE ###

# 解答ちらっと見た
# 問題のキモは Cx,Cy,Hがそれぞれ100通り、
# 全探索をCx,Cy,Hに対して試みると 入力された情報のcheckを入れて101*101*100*100でTLEする。
# でもよく考えてみると、Cx,CyがわかればHはそのあとで出せるので Cx,Cyに対して全探索をする(101*101*100+100の計算量で済む)


def get_H(Cx, Cy):
    for x, y, h in L:
        if h > 0:
            return abs(x - Cx) + abs(y - Cy) + h


def check_H(Cx, Cy, H):
    for x, y, h in L:
        if h != max(H - abs(x - Cx) - abs(y - Cy), 0):
            return False
    return True


N = int(input())

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

for Cx in range(101):
    for Cy in range(101):
        H = get_H(Cx, Cy)
        if check_H(Cx, Cy, H):
            print('{} {} {}'.format(Cx, Cy, H))
            exit(0)
a = input()
print("Yes" if a[1]==a[2]==a[0] or a[1]==a[2]==a[3], else "No")

### FIXED CODE ###

a = input()
print("Yes" if a[0]==a[1]==a[2] or a[1]==a[2]==a[3] else "No")
n=int(input())
dat=list(map(int, input().split()))

for e in dat:
       e = bin(e)[2:]
       e = list(e).reverse()

re = []

for e in dat:
      try:
          w=e.index('1')
          re.append(w)
      except RintimeError:
          re.append(0)

print(min(re))
         
       

print(1)

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
s = input().strip()
t = input().strip()

if t in s:
    print(0)
else:
    ans = 1000
    for i in range(len(s) - len(t) - 1):
        count = len(t) - 1
        for j in range(len(t) - 1):
            if s[i + j] == t[i]:
                count -= 1
        ans = min(count, ans)
    print(ans)


### FIXED CODE ###

s = input().strip()
t = input().strip()

if t in s:
    print(0)
else:
    ans = 10001
    for i in range(len(s) - len(t) + 1):
        count = 0
        cnt = i
        for j in range(len(t)):
            if s[cnt] != t[j]:
                count += 1
            cnt += 1
        ans = min(count, ans)
    print(ans)
n = int(input())
    if n == 1:
        print("Hello World")
    elif n == 2:
        a = int(input())
        b = int(input())
        print(a+b)

### FIXED CODE ###

n = int(input())
if n == 1:
    print("Hello World")
elif n == 2:
    a = int(input())
    b = int(input())
    print(a + b)
from queue import PriorityQueue as PQ
INF = float('inf')
def pcc(src):
	pq = PQ()
	global n
	dist = [INF]*(n+1)
	dist[src] = 0
	pq.put([0,src])
	while not pq.empty():
		d,u = pq.get()
		for w,v in adj[u]:
			if dist[v] > dist[u]+w:
				dist[v] = dist[u]+w
				pq.put([dist[v], v])
	return dist

n,m,src=(int(i) for i in input().split())
adj = {}
for i in range(n+1): adj[i] = []
for i in range(m):
	u,v,w = (int(i) for i in input().split())
	adj[u].append([w,v])
	adj[v].append([w,u])

dist = pcc(src)

for i in range(n):
	print(i,"\t",dist[i])


### FIXED CODE ###

import heapq
def dijkstra(s, neighbor):
	dist = [float('inf')] * N
	dist[s] = 0
	que = [(0, s)]
	heapq.heapify(que)
	while que:
		d, v = heapq.heappop(que)
		if d > dist[v]:
			continue
		for u, l in neighbor[v]:
			tmp_d = d + l
			if tmp_d < dist[u]:
				dist[u] = tmp_d
				heapq.heappush(que, (tmp_d, u))
	return dist
 
N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
	u, v, a, b = map(int, input().split())
	yen[u-1].append((v-1, a))
	yen[v-1].append((u-1, a))
	snuuk[u-1].append((v-1, b))
	snuuk[v-1].append((u-1, b))
 
dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
	if dist_s[i] + dist_t[i] < tmp:
		tmp = dist_s[i] + dist_t[i]
	ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')
import sys
readline = sys.stdin.readline

MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(1341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD

def accumulate2d(X2):
    X = X2
    N = len(X)
    M = len(X[0])
    
    for i in range(N):
        for j in range(1, M):
            X[i][j] += X[i][j-1]
    
    for j in range(M):
        for i in range(1, N):
            X[i][j] += X[i-1][j]
    
    return X

r1, c1, r2, c2 = map(int, readline().split())

def calc(R, C):
    if min(R, C) == 0:
        return 1
    res = R
    for i in range(1, C):
        res = (res + comb(R+i, i+1)) % MOD
    return res
r2 += 1
c2 += 1
print((calc(r2, c2)-calc(r2, c1)-calc(r1, c2)+calc(r1, c1))%MOD)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(2341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD

def accumulate2d(X2):
    X = X2
    N = len(X)
    M = len(X[0])
    
    for i in range(N):
        for j in range(1, M):
            X[i][j] += X[i][j-1]
    
    for j in range(M):
        for i in range(1, N):
            X[i][j] += X[i-1][j]
    
    return X

r1, c1, r2, c2 = map(int, readline().split())

def calc(R, C):
    if min(R, C) == 0:
        return 1
    res = R
    for i in range(1, C):
        res = (res + comb(R+i, i+1)) % MOD
    return res
r2 += 1
c2 += 1
print((calc(r2, c2)-calc(r2, c1)-calc(r1, c2)+calc(r1, c1))%MOD)
N,k= map(int,input().split())
A= list(map(int,input().split()))
tree = [0] * (N+1)
M=10**9+7
def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x&(-x)
def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x&(-x)
    return s

answer = N*(N-1)//2
c={}
for x in A:
    answer -= BIT_sum(tree,x)
    BIT_update(tree,x)
    if x not in c:
        c[x]=1
    else:
        c[x]+=1
c=sorted(c.items(),key=lambda x:x[0])
d,e=0,0
for j in c:
    d+=e
    e+=j[1]
print(((answer*k+d*(((((k-1)*k)//2))%M))%M))

### FIXED CODE ###

n,k=map(int,input().split())
a,b=list(map(int,input().split())),0
for i,j in enumerate(a):
    for h in a[i:]:
        if j<h:b+=k*(k-1)//2
        elif j>h:b+=k*(k+1)//2
print(b%(10**9+7))