Problem:
 Score : 300 points    Problem Statement We have a sequence of N integers A~=~A_0,~A_1,~...,~A_{N - 1} .  Let B be a sequence of K \times N integers obtained by concatenating K copies of A . For example, if A~=~1,~3,~2 and K~=~2 , B~=~1,~3,~2,~1,~3,~2 .  Find the inversion number of B , modulo 10^9 + 7 .  Here the inversion number of B is defined as the number of ordered pairs of integers (i,~j)~(0 \leq i < j \leq K \times N - 1) such that B_i > B_j .      Constraints  All values in input are integers.  1 \leq N \leq 2000  1 \leq K \leq 10^9  1 \leq A_i \leq 2000         Input Input is given from Standard Input in the following format:  N  K  A_0  A_1  ...  A_{N - 1}       Output Print the inversion number of B , modulo 10^9 + 7 .        Sample Input 1 2 2
2 1      Sample Output 1 3  In this case, B~=~2,~1,~2,~1 . We have:   B_0 > B_1  B_0 > B_3  B_2 > B_3   Thus, the inversion number of B is 3 .       Sample Input 2 3 5
1 1 1      Sample Output 2 0  A may contain multiple occurrences of the same number.       Sample Input 3 10 998244353
10 9 8 7 5 6 3 4 2 1      Sample Output 3 185297239  Be sure to print the output modulo 10^9 + 7 .

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, \
array, bisect, sys, random, time, copy, functools, os, queue, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, K = LI()
A = LI()

"""
2 1なら
2 1 2 1
点灯数は、左の数のほうが多いもの
2 1
2 1
2 1
の3種類
2回つなげてみたら決まる
2 1 2 1なら
K = 2で3
K=3 で 2 1 2 1 2 1で6
K=4 で2 1 2 1 2 1 2 1で10通り 4+3+2+1=
K=6なら 2 1 2 1 2 1 2 1 2 1 2 1で6+5+4+3+2+1 = 

偶奇でわける
modで割る

1 2なら
1 2 1 2で1しかない1
1 2 1 2 1 2なら3で2 + 1
1 2 1 2 1 2 1 2 なら6で3+2+1
"""
if len(set(A)) == 1:
    print(0)
    exit()

"""
各数字ごとに数える
"""
K %= mod
in_count = 0
for i in range(N):
    for j in range(i, N):
        if A[i] > A[j]:
            
            in_count += 1

in_count %= mod
in_ans = in_count * K
in_ans %= mod

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


out_count %= mod
out_ans = (out_count * K * (K-1))//2
out_ans %= mod

print(int((in_ans + out_ans)%mod))

Solution (Python):
M = 10**9+7
import sys
input = sys.stdin.readline

N,K = map(int, input().split())
A = list(map(int, input().split()))
A_ = sorted(A, reverse = True)
ans = 0
ans_ = 0
for i in range(0,N-1):
        for j in range(i+1,N):
            if A[i] > A[j]:
                ans += 1
            if A_[i] > A_[j]:
                ans_ += 1

print(((int((K*(K-1))//2)%M)*ans_+ans*K)%M)

Solution (Python):
MAX = 10**9 + 7
_, K = map(int, input().split())
a = list(map(int, input().split()))
s = [sum([b > c for c in a]) for b in a]
r = [sum([b > c for c in a[i:]]) for i, b in enumerate(a)]
b = sum(s)*(K-1)*K//2%MAX
print((b+sum(r)*K)%MAX)

Solution (Python):
N,K= list(map(int, input().split()))
A= list(map(int, input().split()))
AA=sorted(A)
num=0
for i in A:
    num+=AA.index(i)
num2=0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i]>A[j]:
            num2+=1
hoge=(K-1)*K//2%1000000007
hoge=hoge*num%1000000007
hoge2=num2*K%1000000007
hoge=(hoge+hoge2)%1000000007
print(hoge)

Solution (Python):
N, K = map(int, input().split())

A = list(map(int, input().split()))
AA = []
for i in range(2):
    AA.extend(A)

x = 0
for i in range(N):
    for j in range(i+1, N):
        if A[j] < A[i]:
            x += 1
M = 10**9 + 7

y = 0
NN = N*2
for i in range(NN):
    for j in range(i+1, NN):
        if AA[j] < AA[i]:
            y += 1

a = (K*x)
b = (y - 2*x) * (K*(K-1)//2)
ans = ((a+b)  % M)
print(int(ans))

Solution (Python):
n,k=map(int,input().split())
l=list(map(int,input().split()))
A=sorted(l)
x=[];d=[]
m=10**9+7
for i in range(n):
  ct=0
  for j in range(i+1,n):
    if l[i]>l[j]:ct+=1
  x.append(ct)
for i in range(n):
  d.append(A.index(l[i]))
ans=0
for i in range(n):
  ans+=((k*(2*x[i]+(k-1)*d[i]))//2)%m
print(ans%m)

Solution (Python):
N,K= list(map(int, input().split()))
A= list(map(int, input().split()))
AA=sorted(A)
num=0
for i in A:
    num+=AA.index(i)
num2=0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i]>A[j]:
            num2+=1
hoge=(K-1)*K//2%1000000007
hoge=hoge*num%1000000007
hoge2=num2*K%1000000007
hoge=(hoge+hoge2)%1000000007
print(hoge)

Solution (Python):
def main():
    n, k = (int(i) for i in input().split())
    a = [int(i) for i in input().split()]
    MOD = 10**9 + 7
    ans = 0
    alpha = 0
    for i in range(n):
        for j in range(i+1,n):
            if a[i] > a[j]:
                alpha += 1
    ans = ans + (alpha * k)%MOD

    beta = 0
    for i in range(n):
        for j in range(n):
            if a[i] > a[j]:
                beta += 1
    ans = ans + (((k*(k-1)) // 2) * (beta) ) %MOD
    ans = ans % MOD
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N, K = [int(x) for x in input().strip().split()]
A = [int(x) for x in input().strip().split()]
T_A = 0
T_A_all = 0
for i,a in enumerate(A):
    T_A += len([1 for x in A[i+1:] if a > x])
    T_A_all += len([1 for x in A if a > x])
a = T_A
z = T_A + T_A_all * (K -1)
print(int((K*(a+z)//2)%((10**9)+7)))

Solution (Python):
import sys
input = sys.stdin.readline
N, K = [int(x) for x in input().strip().split()]
A = [int(x) for x in input().strip().split()]
T_A = 0
T_A_all = 0
for i,a in enumerate(A):
    T_A += len([1 for x in A[i+1:] if a > x])
    T_A_all += len([1 for x in A if a > x])
a = T_A
z = T_A + T_A_all * (K -1)
print(int((T_A*K+T_A_all*K*(K-1)//2)%((10**9)+7)))

Solution (Python):
n,k=map(int,input().split())
List=list(map(int,input().split()))


li = []

for i in range(n):
    count=0
    for j in range(n):
        if List[i]>List[j]:
            count += 1
    li.append(count)

count2=0

for i in range(1,n):
    for j in range(i+1,n+1):
        if int(List[i-1]) > int(List[j-1]):
            count2 += 1

counted = k*count2 + (sum(li))*k*(k-1)//2

ans = counted % (10**9+7)
print(int(ans))

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
x=0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i]>a[j]:
            x+=1
y = 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            y += 1

ans = x*k + y*k*(k-1)//2
print(ans%(10**9+7))

Solution (Python):
N,K = input().split()
N = int(N)
K = int(K)
mod = 1000000007
ans =0

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

firstcnt = 0
seccnt = 0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i]> A[j]:
            firstcnt += 1
for i in range(N):
    for j in range(N):
        if A[i]> A[j]:
            seccnt += 1


firstcnt =  firstcnt % mod
seccnt = seccnt % mod

a = (firstcnt*K)%mod
c = ((K-1)*K//2)%mod
b = (seccnt * c)%mod

ans = a + b
ans = ans % mod

print(int(ans))

Solution (Python):
import math

def A():
    temp = input().split()
    M = int(temp[0])
    D = int(temp[1])

    if D<22:
        print(0)
        return
    
    ans = 0

    for i in range(1, M+1):
        for j in range(22, D+1):
            if (j%10) >= 2 and (j%10)*int(j/10) == i:
                ans += 1
    
    print(ans)

def B():
    temp = input().split()
    N = int(temp[0])
    K = int(temp[1])
    A = [int(i) for i in input().split()]

    basic_inv = 0
    for i in range(0, len(A)):
        for j in range(i+1, len(A)):
            if A[i] > A[j]:
                basic_inv += 1
    
    if K == 1:
        print(basic_inv)
        return

    inv = 0
    for i in range(0, len(A)):
        for j in range(0, len(A)):
            if A[i] > A[j]:
                inv += 1

    
    s = (K*(K-1))//2
    num = s
    k_mod = K
    print(int(k_mod*basic_inv + num*inv)%(10**9+7))

    
    
    
    
    
    
    
    
    
    

B()

Solution (Python):
def getlist():
	return list(map(int, input().split()))

N, K = getlist()
A = getlist()

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

s = 0
for i in range(N):
	for j in range(N):
		if i != j:
			if A[i] > A[j]:
				s += 1

ans1x = int(((K - 1) * K) // 2) % 1000000007
ans1 = ans1x * s % 1000000007
ans2 = K * x % 1000000007
print((ans1 + ans2) % 1000000007)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
x=0
y=0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      x+=1
for l in range(n):
  for m in range(n):
    if a[l]>a[m]:
      y+=1
ans=((k*(k-1)*y)//2)%(1000000007)+(k*x)%1000000007
print(ans%1000000007)

Solution (Python):
n,k = map(int, input().split())
*a, = map(int, input().split())
ans = 0
wer = 0

for i in range(n-1):
  for j in range(i+1, n):
    if a[i] > a[j]:
      ans += 1
ans *= k

for i in range(n):
  for j in range(n):
    if a[i] > a[j]:
      wer += 1
wer *= k*(k-1)//2

ans += wer
ans %= 10**9 + 7
  
print(ans)

Solution (Python):
N,K = map(int, input().split())
A = list(map(int, input().split()))
sorted_A = sorted(A)

inv_A = 0
for i in range(0,N):
  for j in range(0,N):
    if i<j and A[i] > A[j]:
      inv_A += 1

inv_sorted_A = 0
for i in range(0,N):
  for j in range(0,N):
    if i<j and sorted_A[i] < sorted_A[j]:
      inv_sorted_A += 1

if K == 1:
  print(inv_A)
else:  
  count = inv_sorted_A * K * (K-1) // 2  + inv_A * K 
  print(count % 1000000007)

Solution (Python):
def count_inversion(sequence):
    count = 0
    for i in range(1,len(sequence)):
        for j in range(i,len(sequence)):
            if sequence[i-1] > sequence[j]:
                count += 1
    else:
        count = count%MAX
    return count%MAX

def count_bigger(sequence):
    count = 0
    for num1 in sequence:
        for num2 in sequence:
            if num1 < num2:
                count += 1
    else:
        count = count%MAX
    return count%MAX

MAX = 10**9 +7
N, K = map(int,input().split())
A = list(map(int,input().split()))
ans = (count_bigger(A))%MAX

ans *= (K*(K-1)//2)%MAX
ans += ((K%MAX)*count_inversion(A))%MAX
print(int(ans%MAX))

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

N, K = inpl()
A = inpl()
MOD = 10**9+7
ans = 0
for i in range(N):
    d0 = 0
    d1 = 0
    for j in range(i):
        d0 += A[i] > A[j]
    for j in range(i, N):
        d1 += A[i] > A[j]
    ans = (ans + K*(d1 + d1*K)//2 + (K-1)*(d0 + d0*(K - 1))//2)%MOD

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

l = [0 for _ in range(2*n)]
for j in range(1, 2 * n):
	cnt = 0
	for i in range(j):
		if a[i] > a[j]:
			cnt += 1
	l[j] = cnt
base = sum(l[:n])
inc = sum(l[n:])
inc -= base
if k == 1:
	print(base)
else:
	print((base * k + inc * k * (k - 1) // 2) % (int(1e9 + 7)))

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
c = 0
mod = (int)(1e9+7)
num = [0 for _ in range(2001)]
for v in a:
  num[v]+=1
for i in range(1,2001):
  num[i]+=num[i-1]
s = set(a)
for v in s:
  c += (num[v]-num[v-1])*num[v - 1]
nn = k-1
if (nn%2==0):
  mul = int((nn//2)*(nn-1))
  mul+=nn
else:
  mul = (nn//2 +1)*nn
now = mul*c
now%=mod
total = 0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      total+=1
total*=k
total%mod
final = total+now
print(final%mod)

Solution (Python):
P = (10**9)+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
res_p = 0
res_n = 0

for i in range(N):
    for j in range(i+1,N):
        if A[i]>A[j]:
            res_p += 1
        if A[-i-1]>A[-j-1]:
            res_n += 1
res = (K * res_p)
res += (res_p + res_n) * (K * (K-1) // 2)
print(int(res % P) )

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools
 
INF = 10 ** 10
 
MOD = 10**9 + 7
 
N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
 
 
cnt = 0
 
for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            cnt += 1
 
cnt = cnt % MOD
 
if K >= 2:
    cnt = (cnt * K) % MOD
 
cnt2 = 0
 
if K >= 2:
    for i in range(N):
        for j in range(N):
            if A[i] > A[j]:
                cnt2 += 1
    cnt2 = cnt2 % MOD
 
    tmp = ((K) * (K-1)) // 2
 
    cnt2 = (cnt2 * tmp) % MOD
 
cnt = (cnt + cnt2) % MOD
 
print(cnt)

Solution (Python):
N,K=map(int,input().split())

a=list(map(int,input().split()))
tentou1=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      tentou1+=1
a.sort()
a.reverse()
stentou=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      stentou+=1
answer=tentou1*K + stentou*K*(K-1)//2
print(answer%1000000007)

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

x = 0
for l in range(N - 1):
  for r in range(l + 1, N):
    if A[l] > A[r]:
      x += 1

      
AA = A + A
y = 0
for l in range(N):
  for r in range(N):
    if AA[l] > AA[r]:
      y += 1

  
print(int((K * x + K * (K - 1) * y // 2) % (10 ** 9 + 7)))

Solution (Python):
N,K =map(int,input().split())
a = list(map(int,input().split()))

count = 0
dis = 0
mod = (10**9+7)
for i in a:
    for k in a:
        if k < i:
            count +=1
        count %= mod
for i in range(N):
    for k in a[i:]:
        if k<a[i]:
            dis += 1
        dis %= mod
print(int((K * dis + K * (K - 1) * count // 2) % mod))

Solution (Python):
import numpy as np
count = np.count_nonzero
N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split())))
div = 1000000007
s = 0
s2 = 0
for i, n in enumerate(A):
    tmp = A < n
    s += count(tmp[i+1:])
    s2 += count(tmp)

print(((s * K) + (s2 * (K-1) * K // 2)) % div)

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 10 ** 9 + 7
max_A = 2000
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]


bit = Bit(max_A)
X = 0
for i, p in enumerate(A):
    bit.add(p, 1)
    X += i + 1 - bit.sum(p)


Y = -X
for i, p in enumerate(A):
    bit.add(p, 1)
    Y += i + N + 1 - bit.sum(p)

ans = (X * K + Y * K * (K - 1) // 2) % mod
print(ans)

Solution (Python):
MOD = 10**9 + 7

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

numInvs = [0] * N
for i, Ai in enumerate(As):
    for Aj in As[i+1:]:
        if Ai > Aj:
            numInvs[i] += 1

nums = [0] * N
for i, Ai in enumerate(As):
    for Aj in As:
        if Ai > Aj:
            nums[i] += 1

ans = 0
for numInv, num in zip(numInvs, nums):
    ans += numInv*K % MOD
    ans += num*K*(K-1)//2 % MOD
    ans %= MOD

print(ans)

Solution (Python):
N,K=map(int,input().split())

a=list(map(int,input().split()))
tentou1=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      tentou1+=1
a.sort()
a.reverse()
stentou=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      stentou+=1
answer=int(tentou1*K + int(stentou*K*(K-1)//2))
print(answer%1000000007)

Solution (Python):
import numpy as np
N, K = list(map(int, input().split()))
A = np.array(list(map(int, input().split())))
div = 1000000007
s = 0
s2 = 0
for i, n in enumerate(A):
    tmp = A < n
    s += np.count_nonzero(tmp[i+1:])
    s2 += np.count_nonzero(tmp)

print(((s * K) + (s2 * (K-1) * K // 2)) % div)

Solution (Python):


n, k = map(int, input().split())
a = list(map(int, input().split()))
_mod = 10**9+7

ca = 0
cb = 0

for i in range(0, n):
    for j in range(i, n):
        if a[i] > a[j]:
            ca += 1
    for l in range(0, n):
        if a[i] > a[l]:
            cb += 1

count = ca * k + cb * (k*(k-1))//2
print(count % _mod)

Solution (Python):


n, k = map(int, input().split())
a = list(map(int, input().split()))
_mod = 10**9+7

ca = 0
cb = 0

for i in range(0, n):
    for j in range(i, n):
        if a[i] > a[j]:
            ca += 1

for i in range(0, n):
    for l in range(0, n):
        if a[i] > a[l]:
            cb += 1

count = ca * k + cb * (k*(k-1))//2
print(count % _mod)

Solution (Python):
import sys
input = sys.stdin.readline

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

mod = 10**9+7
li = [0]*n
li2 = [0]*n

for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            li[i] += 1
            if i < j:
                li2[i] += 1

print((sum(li2)*k+sum(li)*(k-1)*k//2)%mod)

Solution (Python):
n, k = list(map(int, input().split()))
a = list( map(int, input().split())) 

MOD = 10**9 + 7

ansR = 0
ansL = 0

for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i > j:
                ansL += 1
            if i < j:
                ansR += 1

ans = ansR*(k+1)*k//2%MOD + ansL*(k-1)*k//2%MOD

print(int(ans%MOD))

Solution (Python):
a,b=map(int,input().split())
c=list(map(int,input().split()))
ans=0
mod=10**9+7
for i in range(a):
  for j in range(a):
    if c[i]>c[j]:
      if i<j:
        ans+=(b*(b+1)//2)%mod
      else:
        ans+=(b*(b-1)//2)%mod
        
print(ans%mod)

Solution (Python):
def count_inversion(sequence):
    count = 0
    for i in range(1,len(sequence)):
        for j in range(i,len(sequence)):
            if sequence[i-1] > sequence[j]:
                count += 1
    else:
        count = count%MAX
    return count%MAX

def count_bigger(sequence):
    count = 0
    for num1 in sequence:
        for num2 in sequence:
            if num1 < num2:
                count += 1
    else:
        count = count%MAX
    return count%MAX

MAX = 10**9 +7
N, K = map(int,input().split())
A = list(map(int,input().split()))
ans = (count_bigger(A))%MAX

ans *= (K*(K-1)//2)%MAX
ans += ((K%MAX)*count_inversion(A))%MAX
print(int(ans%MAX))

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

mod = 10**9 + 7
intra, inter = 0, 0
for i in range(N):
    ai = A[i]
    for j in range(i, N):
        aj = A[j]
        if ai > aj:
            intra += 1
    for j in range(i + 1):
        aj = A[j]
        if ai > aj:
            inter += 1

ans = (intra * K * (K + 1) // 2) % mod
ans += (inter * (K - 1) * K // 2) % mod
print(ans % mod)

Solution (Python):
import numpy as np
N, K   = map(int, input().split())
A=np.array(list(map(int, input().split())))
right=[]
left=[]
for i in range(N):
    right.append(np.count_nonzero(A[i:] < A[i]))
    left.append(np.count_nonzero(A[:i] < A[i]))
ans=sum(right)*(K*(1+K)//2)+sum(left)*((K-1)*K//2)
print(ans%(10**9+7))

Solution (Python):
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
g = {}
ans = 0
for i, a in enumerate(A):
    g[a] = N
    for j, b in enumerate(A):
        if a < b:
            g[a] -= 1
        if  i < j and a > b:
            ans += 1

ans = ans * K
S = (K * (K-1))//2
m = 10**9 + 7
for v in A:
    i = g[v]
    ans += S * (N - i) % m

print(ans % m)

Solution (Python):
N,K=map(int,input().split())

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


all_value = {i:0 for i in input_list}
for i in set(input_list):
    for j in input_list:
        if i> j:
            all_value[i]+=1

            
first_value = {i:0 for i in range(len(input_list))}

for i in range(len(input_list)-1):
    for j in range(i,len(input_list)):
        if input_list[i]>input_list[j]:
            first_value[i]+=1





count=0
for pos,i in enumerate(input_list):
    count += first_value[pos]*K+all_value[i]*(K-1)*K//2

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

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  
        return str(list(self))

    def sum(self, i):
        
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        
        self.add(key, value - self[key])

mod = 10**9+7
N, K = map(int, input().split())
A = list(map(int, input().split()))
bit = Bit(max(A)+1)
ans = 0
for i, a in enumerate(A):
    ans += i - bit.sum(a+1)
    bit.add(a, 1)
ans *= K
from itertools import combinations
cnt = 0
for a, b in combinations(A, 2):
    if a!=b:
        cnt += 1
cnt *= K*(K-1)//2
ans += cnt
print(ans%mod)

Solution (Python):
import sys

input = sys.stdin.readline

MOD = 10 ** 9 + 7

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

a_single = 0
a_multi = 0

for i, ai in enumerate(a):
    for j, aj in enumerate(a):
        if ai > aj:
            a_multi += 1
            if j > i:
                a_single += 1

ans = 0
ans = (a_single * k % MOD + ans) % MOD
ans = (k * (k - 1) // 2 % MOD * a_multi % MOD + ans) % MOD

print(ans)

Solution (Python):
N,K = [int(i) for i in input().split()]
A_list = [int(i) for i in input().split()]

mod = 10**9+7


rightlist = [0 for i in A_list]
alllist = [0 for i in A_list]

for i in range(len(A_list)):
    ct1 = 0
    ct2 = 0
    a = A_list[i]
    right = A_list[i:]
    
    for j in right:
        
        if a > j:
            ct1+=1
    
    for j in A_list:
        if a > j:
            ct2+=1
    rightlist[i] = ct1
    alllist[i] = ct2


R = int(sum(rightlist))
A  =int(sum(alllist))
K = int(K%mod)
R = int(R%mod)
A = int(A%mod)

ans = int(int(R*K)+A*int(K*(K-1)//2))
print(ans%mod)

Solution (Python):
n,k = map(int,input().split())
a_list = list(map(int,input().split()))
count = 0
for i in range(n):
    for j in range(i,n):
        if a_list[i] > a_list[j]:
            count += 1

tmp_list = [0]*n
for i in range(n):
    cnt = 0
    for a in a_list:
        if a_list[i] > a:
            cnt += 1
    tmp_list[i] = cnt
res = k * (2*count + sum(tmp_list) * (k-1)) // 2 
print(res % (10**9+7))

Solution (Python):
import sys

stdin = sys.stdin

sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

def f(n):
  return n*(n+1)//2

x = 0
y = 0

n, k = an()
a = list(an())

mod = int(1e9)+7
ans = 0

for i, ai in enumerate(a):
  for j in range(i+1, n):
    if ai > a[j]:
      x += 1
  
  for j in range(i+1):
    if ai > a[j]:
      y += 1

ans += x * f(k)
ans += y * f(k - 1)
print(ans % mod)

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

MOD = 10**9 + 7

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]


cnt = 0

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

cnt = cnt % MOD

cnt2 = 0

if K >= 2:
    for i in range(N):
        for j in range(N):
            if A[i] > A[j]:
                cnt2 += 1

    cnt2 = cnt2 % MOD

ans = cnt*K + cnt2*((K*(K-1))//2)
ans %= MOD
print(ans)

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

AA = A + A

AA_re = list(reversed(AA))
A_re = list(reversed(A))

ans0 = 0
for i in range(N):
    a = A_re[i]
    for j in range(i + 1, N):
        b = A_re[j]
        if a < b:
            ans0 += 1


ans1 = 0
for i in range(N):
    a = AA_re[i]
    for j in range(i + 1, 2 * N):
        b = AA_re[j]
        if a < b:
            ans1 += 1


sa = ans1 - ans0
m = 10 ** 9 + 7
matu = ans0 + sa * (K - 1)
ans = (ans0 + matu) * K // 2

if K == 0:
    print(int(ans0))
    exit()

ans = ans % m


print(int(ans))

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))

t1 = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] > a[j]:
            t1 += 1

t2 = 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            t2 += 1

ans = t1 * k + t2 * k * (k - 1) // 2

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

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

AA = A + A

AA_re = list(reversed(AA))
A_re = list(reversed(A))

ans0 = 0
for i in range(N):
    a = A_re[i]
    for j in range(i + 1, N):
        b = A_re[j]
        if a < b:
            ans0 += 1


ans1 = 0
for i in range(N):
    a = AA_re[i]
    for j in range(i + 1, 2 * N):
        b = AA_re[j]
        if a < b:
            ans1 += 1


sa = ans1 - ans0
m = 10 ** 9 + 7


matu = ans0 + sa * (K - 1)
c = ans0 + matu

ans = c * K // 2

if K == 0:
    print(int(ans0))
    exit()

ans = ans % m


print(int(ans))

Solution (Python):
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
a = sum([sum([1 for j in range(i) if A[i]<A[j]]) for i in range(N)])
b = sum([sum([1 for j in range(N) if A[i]<A[j]]) for i in range(N)])
print((a*K+b*K*(K-1)//2)%(10**9+7))

Solution (Python):
N,K=map(int,input().split())

a=list(map(int,input().split()))
tentou1=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      tentou1+=1
a.sort()
a.reverse()
stentou=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      stentou+=1
answer=int(tentou1*K + int(stentou*K*(K-1)//2))
print(answer%1000000007)

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

AA = A + A

AA_re = list(reversed(AA))
A_re = list(reversed(A))

ans0 = 0
for i in range(N):
    a = A_re[i]
    for j in range(i + 1, N):
        b = A_re[j]
        if a < b:
            ans0 += 1


ans1 = 0
for i in range(N):
    a = AA_re[i]
    for j in range(i + 1, 2 * N):
        b = AA_re[j]
        if a < b:
            ans1 += 1


sa = ans1 - ans0
m = 10 ** 9 + 7
matu = ans0 + sa * (K - 1)
ans = (ans0 + matu) * K // 2

if K == 0:
    print(int(ans0))
    exit()

ans = ans % m


print(int(ans))

Solution (Python):
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
div = 1000000007
s = 0
ss = 0

for i, a in enumerate(A):
    for j in A[i+1:]:
        if a > j:
            s += 1

for i in A:
    for j in A:
        if i > j:
            ss += 1

print(((s * K) + (ss * K * (K-1) // 2)) % div)

Solution (Python):
def main():
    M=10**9+7
    n,k=map(int,input().split())
    r1=k*(k+1)//2%M
    r2=k*(k-1)//2%M
    *a,=map(int,input().split())
    ans=0
    for i,t in enumerate(a):
        tem=0
        for j,u in enumerate(a):
            if u<t:
                if j<i:tem+=r2
                else:tem+=r1
        ans+=tem
        ans%=M
    print(ans)
main()

Solution (Python):
M = 10**9+7
import sys
input = sys.stdin.readline
def main():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))
    A_ = sorted(A, reverse = True)
    ans = 0
    ans_ = 0
    for i in range(0,N-1):
        for j in range(i+1,N):
            if A[i] > A[j]:
                ans += 1
            if A_[i] > A_[j]:
                ans_ += 1

    print(int((((K*(K-1)//2)%M)*ans_+ans*K)%M))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
n,k=map(int,input().split())
a=list(map(int,input().split()))
b,c=0,0
mod=10**9+7
for i in range(n):
    for j in range(i+1,n):
        if a[i]>a[j]:
            b+=1
    for j in range(i):
        if a[i]>a[j]:
            c+=1

print((b*k*(k+1)//2+c*(k-1)*k//2)%mod)

Solution (Python):
n, k = list(map(int, input().split()))
a = list( map(int, input().split())) 

MOD = 10**9 + 7

ansR = 0
ansL = 0

for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i > j:
                ansL += 1
            if i < j:
                ansR += 1


ansR %= MOD
ansL %= MOD
Rn = (k+1)*k//2%MOD
Ln = (k-1)*k//2%MOD

ans = int(ansR*Rn)%MOD + int(ansL*Ln)%MOD

print(int(ans%MOD))

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))

ans1 = 0
for i in range(n):
    for j in range(i+1, n):
        if a[i] > a[j]:
            ans1 += 1

ans2 = 0
for i in a:
    for j in a:
        if i > j:
            ans2 += 1

ans = k * ans1 + k * (k-1) // 2 * ans2
ans %= 10 ** 9 + 7

print(ans)

Solution (Python):
N,K=map(int,input().split())
 
a=list(map(int,input().split()))
tentou1=0
for i in range(N):
  for j in range(i+1,N):
    if(a[i]>a[j]):
      tentou1+=1
stentou=0
for i in range(N):
  for j in range(N):
    if(a[i]>a[j]):
      stentou+=1
answer=int(tentou1*K + stentou*K*(K-1)//int(2))
print(answer%1000000007)

Solution (Python):
import sys

stdin = sys.stdin

sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

def f(n):
    return n*(n+1)//2

def main():
  n, k = an()
  a = list(an())

  mod = int(1e9)+7
  ans = 0
  x = a[:] 
  cnt = 0
  tcnt = 0
  for i, ai in enumerate(x):
    
    for j in range(i+1, n):
      if ai > x[j]:
        cnt += 1
    
    for j in range(i+1):
      if ai > x[j]:
        tcnt += 1

  ans += f(k) * cnt
  ans %= mod
  ans += f(k - 1) * tcnt
  ans %= mod

  print(ans)

main()

Solution (Python):
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

g = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        elif i >= j:
            continue
        if a[i] > a[j]:
            
            g += 1

if k == 1:
    print(g)
    exit()
    
a2 = []

for i in range(2*n):
    a2.append(a[i%n])
    
f = 0

for i in range(n):
    for j in range(2*n):
        if i == j:
            continue
        elif i >= j:
            continue
        if a2[i] > a2[j]:
            
            f += 1

t = int((f-g)%mod)
k = int(k%mod)







ans1 = int((k*g%mod)%mod)


ans2 = int(t*(((k-1)%mod*k%mod)%mod)//2%mod)
ans = g*k + t*k*(k-1)//2
print( ans%mod)

exit()

Solution (Python):
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
div = 1000000007
s = 0
ss = 0

for i, a in enumerate(A):
    for j in range(i+1, N):
        if a > A[j]:
            s += 1

for i in A:
    for j in A:
        if i > j:
            ss += 1

print(((s * K) + (ss * K * (K-1) // 2)) % div)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
rcount=0
lcount=0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      rcount+=1

for i in range(n-1):
  for j in range(i+1,n):
    if a[i]<a[j]:
      lcount+=1

mod=10**9+7

print((k*(k+1)*rcount+k*(k-1)*lcount)//2%mod)

Solution (Python):
N,K=map(int,input().split())
 
a=list(map(int,input().split()))
tentou1=0
for i in range(N):
  for j in range(i+1,N):
    if a[i]>a[j]:
      tentou1+=1
stentou=0
for i in range(N):
  for j in range(N):
    if a[i]>a[j]:
      stentou+=1
answer= (tentou1*K) + (K*(K-1)//2*stentou)
print(answer%(10**9+7))

Solution (Python):
P = (10**9)+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
res_p = 0
res_n = 0

for i in range(N):
    for j in range(i+1,N):
        if A[i]>A[j]:
            res_p += 1
        if A[-i-1]>A[-j-1]:
            res_n += 1
res = (res_p + res_n) * K * (K+1) // 2 - (K * res_n)


print(res % P)