Harryxun/stf_run huggingface dataset:
from collections import deque

n,m=map(int,input().split())
L=[[] for i in range(n)]
for i in range(m):
	L[a-1].append(b-1)
	L[b-1].append(a-1)
D=[float('inf') for i in range(n)]

def bfs():
	que=deque([])
	que.append(0)
	D[p]=0
	while que:
		p=que.popleft()
		for np in L[p]:
			if D[np]==float('inf'):
				que.append(np)
				D[np]=p

bfs()

if sum(D)==float('inf'):
	print('No')
else:
	print('Yes')
	for i in range(1,n):
		print(D[i])

### FIXED CODE ###

from collections import deque

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

#print(L)

for i in range(m):
    a,b=map(int,input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)

#print(L)
d=[float('inf') for i in range(n)]
m=[0 for i in range(n)]

def bfs():

    que=deque([])
    que.append(0)
    d[0]=0
    
    while que:
        p=que.popleft()
        for np in L[p]:
            if d[np]==float('inf'):
                que.append(np)
                d[np]=d[p]+1
                m[np]=p+1

bfs()
if sum(d)==float('inf'):
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(m[i])
N,Y = map(int,input().split(" "))
K = Y//1000 -N
     
l = int(-K/4)
if l <= -2*K/9:
    a = K+4*l
    b = -2*K-9*l
    c = N-a-b
    if c >=0:

        print(a," ",b," ",c)
     else:
        print(-1," ",-1," ",-1)
else:
    print(-1," ",-1," ",-1)



### FIXED CODE ###

N,Y = map(int,input().split(" "))
K = Y//1000 -N
     
l = int(-K/4)-1
r = -(2*K)/9+1

if l<=r:
    i=l
    while i <=r:
        a = K+4*i
        b = -2*K-9*i
        c = N-a-b

        if a>=0 and b>=0 and c >=0:
            print(a," ",b," ",c)
            break

        i+=1
    else:
        print(-1," ",-1," ",-1)

else:
    print(-1," ",-1," ",-1)
z=list(map(int,input().split()))
z.sort()
a=0

while True:
    a=z[1]-z[0]
    if z[0]%a==0:
        z[1] = z[0]
        z[0] = a
        z.sort()
        break
    z[1]=z[0]
    z[0]=a
    z.sort()

print(z[0])

### FIXED CODE ###

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

a,b=list(map(int,input().split()))
print(gcd(a,b))
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
BC = []

for i in range(M):
  bc = [int(i) for i in input().split()]
  BC.append(bc)

BC = sorted(BC, key=lambda x: x[1])
BC.reverse()

k = 0
for i in BC:
  if k = N:
    break
  if i[1] <= A[k]:
    break
  for j in range(i[0]):
    if i[1] > A[k]:
      A[k] = i[1]
      k += 1
    else:
      break

print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
BC = []

for i in range(M):
  bc = [int(i) for i in input().split()]
  BC.append(bc)

BC = sorted(BC, key=lambda x: x[1])
BC.reverse()

k = 0
for i in BC:
  if k == N:
    break
  if i[1] <= A[k]:
    break
  for j in range(i[0]):
    if k == N:
      break
    if i[1] > A[k]:
      A[k] = i[1]
      k += 1
    else:
      break

print(sum(A))
import math
N = int(input())
A = list(map(int, input().split()))


def lcm(a, b):
    y = a * b // math.gcd(a, b)
    return y


c = 0
for i, a in enumerate(A):
    if i == 0:
        c = a
    else:
        c = lcm(c, a)

result = 0
for a in A:
    result += c // a

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

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


def lcm(a, b):
    y = a * b // gcd(a, b)
    return y


c = 0
for i, a in enumerate(A):
    if i == 0:
        c = a
    else:
        c = lcm(c, a)

result = 0
for a in A:
    result += c // a

print(result % (10 ** 9 + 7))
x = int(input()).split()
a = int(x[0])
b = int(x[1])

if a < b:
  print('a < b')
if a > b:
  print('a > b')
if a == b:
  print('a == b')

### FIXED CODE ###

x = input().split()
i = list(map(int,x))
a = i[0]
b = i[1]

if a > b:
  print('a > b')
elif a == b:
  print('a == b')
else:
  print('a < b')
(a, b) = [int(i) for i in input().split(' ')]  
print( repr(a // b) +" "+ repr(a % b) +" "+ ('%0.5f' % (a / b))

### FIXED CODE ###

(a, b) = [int(i) for i in input().split(' ')]  
print( repr(a // b) +" "+ repr(a % b) +" "+ ('%0.5f' % (a / b)))
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
p, n = [], []

for Ai in A:
    if Ai>=0:
        p.append(Ai)
    else:
        n.append(Ai)

if len(n)==N and K%2==1:
    n.sort(reverse=True)
    ans = 1
    
    for ni in n[:K]:
        ans *= ni
        ans %= MOD
    
    print(ans)
    exit()

if K==N and len(n)%2==1:
    for Ai in A:
        ans *= Ai
        ans %= MOD
    
    print(ans)
    exit()

p.sort(reverse=True)
n.sort()
l = []

if K%2==1:
    ans = p[0]
    p = p[1:]
else:
    ans = 1
    
for i in range(len(p)//2):
    l.append(p[2*i]*p[2*i+1])
    
for i in range(len(n)//2):
    l.append(n[2*i]*n[2*i+1])
    
l.sort(reverse=True)
    
for li in l[:K//2]:
    ans *= li
    ans %= MOD
    
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
p, n = [], []

for i in range(N):
    if A[i]>=0:
        p.append(A[i])
    else:
        n.append(A[i])

ok = False

if len(p)>0:
    if N==K:
        if len(n)%2==0:
            ok = True
    else:
        ok = True
else:
    if K%2==0:
        ok = True

if not ok:
    A.sort(key=lambda x: abs(x))
    ans = 1
    
    for Ai in A[:K]:
        ans *= Ai
        ans %= MOD

    print(ans)
    exit()

p.sort(reverse=True)
n.sort()

if K%2==1:
    ans = p[0]
    p = p[1:]
else:
    ans = 1
    
l = []
    
for i in range(len(p)//2):
    l.append(p[2*i]*p[2*i+1])
    
for i in range(len(n)//2):
    l.append(n[2*i]*n[2*i+1])

l.sort(key=lambda x: abs(x), reverse=True)

for li in l[:K//2]:
    ans *= li
    ans %= MOD
    
print(ans)
#D-XXOR

n,k=map(int,input().split())
lists=list(map(int,input().split()))
a=format(k,"b")
length=max(len(a),len(format(max(lists),"b")))
uselists=[0]*length
for some in lists:
    check=format(some,"0%ib"%length)
    for i in range(length):
        if check[i]=="1":
            uselists[length-1-i]+=1         
if k>=1:
    for i in range(length):
        if  2**i<=k<2**(i+1):
            order=i
            break            
    ans1=0
    
    ans2=0
    for j in range(order):
        ans1+=(2**j)*max(uselists[j],n-uselists[j])
    for j in range(order+1,length):
        ans2+=(2**j)*uselists[j]
        
    ans2+=(2**order)*(n-uselists[order])
    bigger=0
    listss=[0]*(k-2**order+1)
    for g in range(0,k-2**order+1):
        some=format(g,"0%ib"%order)
        listss[g]=some

    for some in listss:
        checker=0
        for i in range(order):
            if some[i]=="1":
                checker+=(2**(order-1-i))*(n-uselists[i])
            else:
                checker+=(2**(order-1-i))*uselists[i]
        bigger=max(bigger,checker)
    ans2=ans2+bigger

    print(max(ans1,ans2))
    
elif k==0:
    ans=0
    for i in range(length):
        if uselists[i]=="1":
            ans+=(2**i)*(n-uselists[i])
        else:
            ans+=(2**i)*uselists[i]
            
    print(ans)
        

### FIXED CODE ###

n,k=map(int,input().split())
k2=format(k+1,"0%ib"%40)
lists=list(map(int,input().split()))
countlist=[0]*40
for j in lists:
    c=format(j,"0%ib"%40)
    for i in range(40):
        if c[i]=="1":
            countlist[i]+=1

emptylist=[]
for i in range(40):
    if k2[i]=="1":
        emptylist.append(i)
if k>=1:
    ans=0
    for i in emptylist:
        subing=0
        for j in range(40):
            if j<i:
                if k2[j]=="1":
                    subing+=(2**(39-j))*(n-countlist[j])
                elif k2[j]=="0":
                    subing+=(2**(39-j))*countlist[j]
            if j==i:
                subing+=(2**(39-i))*countlist[i]
            
            if j>i:
                subing+=(2**(39-j))*max(countlist[j],n-countlist[j])
        ans=max(ans,subing)
    print(ans)
elif k==0:
    ans=0
    for i in range(40):
        ans+=(2**(39-i))*countlist[i]
    print(ans)
# coding: utf-8
minutes = [int(input()) for _ in range(5)]
time=0
l=[]

for i in minutes:
    time = time + i
    if(i%10==0):
        l.append(0)
    else:
        l.append(10-i%10)

l.sort()
time = time + sum(l[:-1])
print(time)

### FIXED CODE ###

# coding: utf-8
n = int(input())

high = list(map(int, input().split()))
max_high = []
count =1

for i in range(1,n):
    x = high[:i]
    if(max(x) <= high[i]):
        count = count +1
        
print(count)
N = int(input())
X = list(map(int, input().split()))
X_max = max(X)
ans = float('inf')
for i in range(X_max + 1):
    tmp_ans = 0
    for x in X:
        tmp_ans += (x - i) ** 2
    if tmp_ans < ans:
        ans = tmp_ans
print(ans)


### FIXED CODE ###

N , R = map(int,input().split())
if N < 10:
    print(100 * (10 - N) + R)
else:
    print(R)
s = list(input())

kws = ["dream", "dreamer", "erase", "eraser"]

def func(s):
  bool = False
  for kw in kws:
    if s.startswith(kw):
      bool = bool or func(s[len(kw):])
  return bool

result = func(s)

if result:
  print("YES")
else:
  print("NO")


### FIXED CODE ###

s_list = list(input())

kws = [list(kw) for kw in ["dream", "dreamer", "erase", "eraser"]]

memo = [0 for _ in range(len(s_list)+1)]
memo[0] = 1
for i in range(len(s_list)):
    if memo[i] == 1:
        for kw in kws:
            l = len(kw)
            if s_list[i:i+l] == kw:
                memo[i+l] = 1

if memo[-1] == 1:
    print("YES")
else:
    print('NO')
import numpy as np
import math

_, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

logk = 50
half = len(a) / 2

base = np.array([2**i for i in range(logk + 1)])

a = np.array(a)

ones = a[:,None] & base > 0
zeros = (ones != True)

# print(base[:5])
# print(ones)
# print(zeros)

no = np.sum(ones, axis=0)
nz = np.sum(zeros, axis=0)

ov = no * base
zv = nz * base

# print(no)
# print(nz)

inc = no < half
# vi = np.sum(v * base)


def largest(fx, kk, i):
    if i == len(base):
        return fx

    kone = kk + base[i]
    if kone > k:
        return fx

    kzero = kk
    fzero = fx + ov[i]
    fone = fx + zv[i]
    return max(largest(fzero, kzero, i + 1), largest(fone, kone, i + 1))

print(largest(0, 0, 0))


# print(np.sum(a ^ vi))


### FIXED CODE ###

import numpy as np
import math

_, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

logk = 50
half = len(a) / 2

base = np.array([2**i for i in range(logk + 1)])

a = np.array(a)

ones = a[:,None] & base > 0
zeros = (ones != True)

# print(base[:5])
# print(ones)
# print(zeros)

no = np.sum(ones, axis=0)
nz = np.sum(zeros, axis=0)

ov = no * base
zv = nz * base

# print(no)
# print(nz)

inc = ov < zv

inceq = ov == zv
# vi = np.sum(v * base)


# def largest(fx, kk, i):
#     if i == len(base):
#         return fx

#     kone = kk + base[i]
#     if kone > k:
#         return fx

#     kzero = kk
#     fzero = fx + ov[i]
#     fone = fx + zv[i]
#     return max(largest(fzero, kzero, i + 1), largest(fone, kone, i + 1))

# print(largest(0, 0, 0))

kk = [0]
fx = [0]
for i, b in reversed(list(enumerate(base))):
    for j in range(len(fx)):
        added = kk[j] + b
        if (inc[i] or inceq[i]) and added <= k:
            if inceq[i]:
                fx.append(fx[j] + ov[i])
                kk.append(kk[j])
            fx[j] += zv[i]
            kk[j] += b

        else:
            fx[j] += ov[i]

print(max(fx))
A = input()
B = input()
C = input()


if B != C {
	surplus = A - B
	result = C - surplus 
	print(result)
} else { 
	 print(0)
}

### FIXED CODE ###


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

ans = c - (a - b)
if ans < 0:
	ans = 0
print(ans)
n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range(2,300003):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
        n_c=min(n_a,n_b)
        n_a, n_b=n_a-min(n_a,n_b), n_b-min(n_a,n_b)
        count=0
        while n_a + n_b + n_c <=n and n_c>=0 and n_b>=0 and n_a>=0:
#            ans+=com(n, n_c, mod) * com(n-n_c, n_b, mod) * com(n-n_c-n_b, n_a, mod) %mod
            if count==0:
                aaa0=com(n, n_c, mod) * com(n-n_c, n_b, mod) * com(n-n_c-n_b, n_a, mod) 
                ans+=aaa0
                count+=1
            n_b+=1
            n_a+=1
            aaa0 = aaa0 * n_c / ( (n_a) * (n_b) * (n-n_c-n_b-n_a) )
            n_c-=1
            if count!=0:
                ans+=aaa

print(ans%mod)

### FIXED CODE ###

n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range(2,300003):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
        if  max(n_a, n_b) <=n:
            ans+=com(n, n_a, mod) * com(n, n_b, mod)  %mod

print(ans%mod)
from bisect import bisect_right

N = int(input())
A = [int(input()) for _ in range(N)]

t = deque([-A[0]])
for a in A[1:]:
    if -a <= -t[0]:
        t.append(-a)
    else:
        t[bisect_right(t, -a)] = -a
print(len(t))


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

t = [A[0]]
for a in A[1:]:
    if t[-1] >= a:
        t.append(a)
        continue
    ok = len(t) - 1
    ng = -1
    while ok - ng > 1:
        m = (ok + ng) // 2
        if t[m] < a:
            ok = m
        else:
            ng = m
    t[ok] = a
print(len(t))
# -*- coding:UTF-8 -*-
import sys

print(int(sys.argv[1]) ** 3)
print("Hello World")

### FIXED CODE ###

# -*- coding:UTF-8 -*-
print(int(input()) ** 3)
a, b, c = map(int, input().split())
if (c-a-b)**2 > 4*a*b:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

k = int(input())
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(l[k-1])
s = str(input(""))
t = str(input(""))

print(t + s)

### FIXED CODE ###

s, t = input().split()
print(t + s)
n = list(map(int,input().split()))
n.sorted()
if n[0] + n[1] == n[2]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = list(map(int,input().split()))
n.sort()
if n[0] + n[1] == n[2]:
    print("Yes")
else:
    print("No")
N, M = map(int, input().split())
X_list = list(map(int, input().split()))
X_list.sort()
err_list = [X_list[i+1] - X_list[i] for i in range(len(X_list)-1)]
err_list.sort()

if N == 1:
    print(sum(err_list))
else:
    print(sum(err_list[:-(N-1)]))


### FIXED CODE ###

T, X = map(int, input().split())

print(T/X)
n=int(input())
a=[0]*(n-1)
b=[0]*(n-1)
c=[0]*(n-1)
for _ in range(n-1):
    a,b,c=map(int,input().split())

dp=[[0]*3 for _ in range(n)]

dp[0] = [a[0],b[0],c[0]]

for i in range(n-1):
    dp[i+1][0]=max(dp[i][1]+a[i+1], dp[i][2]＋a[i＋1])
    dp[i+1][1]=max(dp[i][0]+b[i+1], dp[i][2]＋b[i＋1])
    dp[i+1][2]=max(dp[i][0]+c[i+1], dp[i][1]＋c[i＋1])
print(max(dp[n-1]))

### FIXED CODE ###

n=int(input())
a=[0]*(n)
b=[0]*(n)
c=[0]*(n)
for _ in range(n):
    a[_],b[_],c[_]=map(int,input().split())

dp=[[0]*3 for _ in range(n)]

dp[0] = [a[0],b[0],c[0]]

for i in range(n-1):
    dp[i+1][0]=max(dp[i][1]+a[i+1], dp[i][2]+a[i+1])
    dp[i+1][1]=max(dp[i][0]+b[i+1], dp[i][2]+b[i+1])
    dp[i+1][2]=max(dp[i][0]+c[i+1], dp[i][1]+c[i+1])
print(max(dp[n-1]))
def resolve():
    N, A, B, C = map(int, input().split())
    S = [input() for _ in range(N)]

    ans = []
    def dfs(now, a, b, c):
        if now == N:
            return True
        if S[now] == "AB":
            if a == 0 and b == 0:
                return False
            if 0 < a and dfs(now+1, a-1, b+1, c):
                ans.append("B")
                return True
            if 0 < b and dfs(now+1, a+1, b-1, c):
                ans.append("A")
                return True
            return False
        if S[now] == "AC":
            if a == 0 and c == 0:
                return False
            if 0 < a and dfs(now+1, a-1, b, c+1):
                ans.append("C")
                return True
            if 0 < c and dfs(now+1, a+1, b, c-1):
                ans.append("A")
                return True
            return False
        if S[now] == "BC":
            if c == 0 and b == 0:
                return False
            if 0 < b and dfs(now+1, a, b-1, c+1):
                ans.append("C")
                return True
            if 0 < c and dfs(now+1, a, b+1, c-1):
                ans.append("B")
                return True
            return False

    dfs(0, A, B, C)
    if len(ans) == 0:
        print("No")
        return
    else:
        print("Yes")
        [print(a) for a in ans[::-1]]


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 
 

def resolve():
    N, A, B, C = map(int, inp().split())
    S = [inpS() for _ in range(N)]
 
    ans = []
    def dfs(now, a, b, c):
        if now == N:
            return True
        if S[now] == "AB":
            if a == 0 and b == 0:
                return False
            if 0 < a and dfs(now+1, a-1, b+1, c):
                ans.append("B")
                return True
            if 0 < b and dfs(now+1, a+1, b-1, c):
                ans.append("A")
                return True
            return False
        if S[now] == "AC":
            if a == 0 and c == 0:
                return False
            if 0 < a and dfs(now+1, a-1, b, c+1):
                ans.append("C")
                return True
            if 0 < c and dfs(now+1, a+1, b, c-1):
                ans.append("A")
                return True
            return False
        if S[now] == "BC":
            if c == 0 and b == 0:
                return False
            if 0 < b and dfs(now+1, a, b-1, c+1):
                ans.append("C")
                return True
            if 0 < c and dfs(now+1, a, b+1, c-1):
                ans.append("B")
                return True
            return False
 
    dfs(0, A, B, C)
    if len(ans) == 0:
        print("No")
        return
    else:
        print("Yes")
        [print(a) for a in ans[::-1]]
 
 
if __name__ == "__main__":
    resolve()
import math
A, B = map(int, input().split())
print(A * B // math.gcd(A, B))

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
    
A, B = map(int, input().split())
print(A * B // gcd(A, B))
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

while True:
    S = reversed(raw_input())
    if S == '0':
        break
    m = [1] + [0 for i in range(10)]
    diff = ans = 0
    even = 1
    for c in S:
        num = int(c)
        diff += num * even
        diff %= 11
        if num != 0:
            ans += m[diff]
        m[diff] += 1
        even *= -1
    print ans


### FIXED CODE ###

while True:
    S = raw_input()[::-1]
    if S == '0' : break
    m = [1] + [0] * 10
    diff = ans = 0
    even = 1
    for c in S:
        num = int(c)
        diff = (diff + num * even) % 11
        if num : ans += m[diff]
        m[diff] += 1
        even *= -1
    print ans
n,k = int(input()).split()
p = list(int(input()).split())

p1 = sorted(p)

temp = 0
for i in p[k] :
  temp += i
  return temp
print(temp)

### FIXED CODE ###

n,k = map(int , input().split( ))
p = list(map(int , input().split( )))
 
p.sort()
 
temp = 0
for i in p[:k] :
  temp += i
print(temp)
import math
a, b = map(int, input().split())
print(a*b//math.gcd(a, b))

### FIXED CODE ###

import fractions
a, b = map(int, input().split())
print(a*b//fractions.gcd(a, b))
from sys import stdin
from math import factorial
n,k = map(int,stdin.readline().rstrip().split())
li = list(map(int,stdin.readline().rstrip().split()))
li_to = li*2
nai = 0
ato = 0
for i in range(len(li)):
    for s in range(i+1,len(li)):
        if li[i] > li[s]:
            nai += 1
    for p in range(len(li),len(li_to)):
        if li[i] > li_to[p]:
            ato += 1
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))
point = 0
point += (nai*k)+(ato*combinations_count(k,2))
print(point%(10**9+7))

### FIXED CODE ###

from sys import stdin
n,k = map(int,stdin.readline().rstrip().split())
li = list(map(int,stdin.readline().rstrip().split()))
nai = 0
ato = 0
point = 0
for i in range(n):
    for s in range(i+1,n):
        if li[i] > li[s]:
            nai += 1
    for v in range(n):
        if li[i] > li[v]:
            ato += 1
point += (nai*k)+(ato*k*(k-1)//2)
print(point%(10**9+7))
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque((i,j))
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] < dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append((hh+k,ww+l))

    return ans

def main():
    anss = 0
    for i in range(h+2):
        for j in range(w+2):
            if A[i][j] == "#":
                continue
            anss = max(anss,bfs(i,j))
    print(anss)
            
main()
    


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque()
    q.append((i,j ))
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] <= dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append((hh+k,ww+l))

    return ans

anss = 0
for i in range(h+2):
    for j in range(w+2):
        if A[i][j] == "#":
            continue
        anss = max(anss,bfs(i,j))
print(anss)
import functools
import fraction

def blcm(x, y):
	return (x*y)//fraction.gcd(x, y)

def slcm(numbers):
	return functools.reduce(blcm, numbers)
	
input()
numbers=list(map(int, input().split()))
num=slcm(numbers)-1
nums=[num%i for i in numbers]
print(sum(nums))


### FIXED CODE ###

import functools
import fractions

def blcm(x, y):
	return (x*y)//fractions.gcd(x, y)

def slcm(numbers):
	return functools.reduce(blcm, numbers)
	
input()
numbers=list(map(int, input().split()))
num=slcm(numbers)-1
nums=[num%i for i in numbers]
print(sum(nums))
N,K = map(int, input().split())
print(K * (k-1)**(N-1))

### FIXED CODE ###

N,K = map(int, input().split())
print(K * (K-1)**(N-1))
input_number = map(int,input())
input_string = input()
if input_number < 3200:
  print(input_number)
else:
  print(input_string)

### FIXED CODE ###

input_number = int(input())
input_string = input()
if input_number < 3200:
    print("red")
else:
    print(input_string)