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):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import *
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    m, d = LI()
    ans = 0
    for i in range(1, m + 1):
        for j in range(10, d + 1):
            if int(str(j)[0]) < 2 or int(str(j)[1]) < 2:
                continue
            if i == int(str(j)[0]) * int(str(j)[1]):
                ans += 1
    print(ans)
    return


def B():
    n, l = LI()
    a = LI()
    d0 = defaultdict(int)
    d1 = defaultdict(int)
    for i in a:
        d0[i] += 1
    for i in range(n):
        b = 0
        for k in range(i+1, n):
            if a[i] > a[k]:
                b += 1
        d1[i] = b
    ans = 0
    d2 = list(d0.items())
    d2.sort()
    d3 = defaultdict(int)
    d = 0
    for key, value in d2:
        d3[key] = d
        d += value
    for i in range(n):
        ans += d3[a[i]] * l * (l-1) // 2 + d1[i] * l
        ans %= mod
    print(ans % mod)
    return


def C():
    n = II()
    s = itertools.product([1, 0], repeat=2 * n)
    a = list(itertools.combinations(range(2*n), 2))
    d = defaultdict(int)
    def dfs(a):
        if len(a) == n:
            lis.append(a)
            return True
        for i in range(n):
            if d[i] == 0:
                d[i] = 1
                for k in range(n):
                    if d[k] == 0:
                        d[k] = 1
                        a.append((i, k))
                        dfs(a)
                        a.remove((i, k))
    lis = []
    dfs([])
    for si in s:
        for di in lis:
            b = list(si[::1])
            for x, y in di:
                for i in range(x, y + 1):
                    b[i] ^= 1
            if sum(b) < 1:
                print(si, di)
                break

    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    B()

Solution (Python):
import bisect
from collections import deque
import sys
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
a = IL()

cnt = 0
for left in range(N):
  for right in range(left+1,N):
    if a[left] > a[right]:
      cnt += 1
cnt = (cnt*K) %mod

a.sort()
tmp = 0
for i in range(N-1):
  if a[i+1] > a[i]:
    tmp = i+1
  cnt += ((tmp*K*(K-1))//2) %mod

print(int(cnt) %mod)

"""
2 1000000006
2 1

10 3
10 9 8 7 6 5 4 3 2 1
"""

Solution (Python):
from collections import Counter

mod = pow(10, 9)+7
n, k = map(int, input().split())
arr = list(map(int, input().split()))

BIT = [0]*(n+1)

def map_arr():
	dct = {}
	idx = 1
	lst = sorted(arr)
	for i in range(n):
		if lst[i] not in dct:
			dct[lst[i]] = idx 
			idx += 1
	return [dct[ele] for ele in arr]

arr = map_arr()
def get_add():
	counter = Counter(arr)
	lst = sorted(counter.items())
	add = lst[0][1]
	dp = [0]*len(lst)
	for i in range(1, len(lst)):
		dp[i] = lst[i-1][1] + dp[i - 1]
	return sum(dp[i]*lst[i][1] for i in range(len(lst)))

def read(idx):
	add = 0
	while idx > 0:
		add += BIT[idx]
		idx -= (-idx & idx)
	return add 

def update(idx):
	while idx <= n:
		BIT[idx] += 1
		idx += (-idx & idx)

inv_count = 0

for i in range(n-1, -1, -1):
	inv_count += read(arr[i]-1)
	update(arr[i])
ans = (k*inv_count)%mod

add = get_add()
multi = (k*(k-1)//2)%mod
ans = (ans + (multi*add)%mod)%mod
print(ans)

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

MOD = 10 ** 9 + 7

X = 0

for i in range(N):
    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 + K*(K-1)//2 * Y) % MOD

print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
if n == 1:
  print("0")
  exit()
ans_unit = 0
for i in range(n-1):
  for j in range(i+1, n):
    if a[i] > a[j]:
      ans_unit+=1
if k == 1:
  print(ans_unit)
  exit()
c = sum([a,a], [])
ans_inc =0
for i in range(0,n):
  for j in range(n, 2*n):
    if c[i] > c[j]:
      ans_inc+=1
ans = (k*ans_unit)%1000000007
if k%2 == 0:
  tmpk = int(k/2)
  tmp_ans = (tmpk*(k-1))%1000000007
else:
  tmpk = int((k-1)/2)
  tmp_ans = (tmpk*(k))%1000000007
tmp_ans *=ans_inc
tmp_ans %=1000000007
ans += tmp_ans
ans = ans%1000000007
print(ans)

Solution (Python):
MOD=10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
n = len(a)
li = [0] * 2001
t1 = 0
for i in range(n):
  for j in range(i + 1, n):
    if a[i] > a[j]:
      t1 += 1
for x in a:
  li[x] += 1
t2 = 0
for i in range(2000):
  t2 += li[i + 1] * li[i]
  li[i + 1] += li[i]
print((t1 * k + t2 * k * (k - 1) // 2) % MOD)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
c=[]
ans=0
for i in range(2002):
    c.append([0,0])
for i in range(n):
    c[a[i]][0]+=1
    for j in range(a[i]+1,2001):
        ans+=c[j][0]
for i in range(1999,-1,-1):
    c[i][0]+=c[i+1][0]
d=0
for i in a:
    d+=c[i+1][0]
print((k*ans+d*(k*(k-1))//2)%mod)

Solution (Python):
MOD=10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
n = len(a)
li = [0] * 2001
t1 = 0
for i in range(n):
  for j in range(i + 1, n):
    if a[i] > a[j]:
      t1 += 1
for x in a:
  li[x] += 1
t2 = 0
for i in range(2000):
  t2 += li[i + 1] * li[i]
  li[i + 1] += li[i]
print((t1 * k + t2 * k * (k - 1) // 2) % MOD)

Solution (Python):
import bisect
from collections import deque
import sys
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
a = IL()

cnt = 0
for left in range(N):
  for right in range(left+1,N):
    if a[left] > a[right]:
      cnt += 1
cnt = (cnt*K) %mod

a.sort()
tmp = 0
for i in range(N-1):
  if a[i+1] > a[i]:
    tmp = i+1
  cnt += ((tmp*K*(K-1))//2) %mod

print(cnt %mod)

"""
2 1000000006
2 1

10 3
10 9 8 7 6 5 4 3 2 1
"""

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



before_cnt = 0

after_cnt = 0
n_list = list(map(int, input().split()))
for i in range(n-1):
  for j in range(i+1, n):
    if n_list[i] > n_list[j]:
      before_cnt+=1
    elif n_list[i] < n_list[j]:
      
      after_cnt+=1
      '''
      if i < j:
        after_cnt+=1
      else:
        before_cnt+=1
'''
kurikaesi = int((1 + k)*k//2)


print(((after_cnt*(kurikaesi-k) + before_cnt*kurikaesi))%(10**9 + 7))

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

left, right = 0, 0
for i in range(len(an)):
    ref = an[i]
    left += len([a for a in an[0:i] if a < ref])
    right += len([a for a in an[i+1:] if a < ref])


k2 = k**2
ans = ((k2 + k) * right + (k2 - k) * left) // 2
print(ans % (10**9 + 7))

Solution (Python):
M, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0
for i, Ai in enumerate(A):
  for Aj in A[i+1:]:
    if Ai > Aj:
      cnt += 1
cnt_sorted = 0
A_sorted = sorted(A, reverse=True)
for i, Ai in enumerate(A_sorted):
  for Aj in A_sorted[i+1:]:
    if Ai > Aj:
      cnt_sorted += 1
ans = cnt * K + cnt_sorted * K * (K-1) // 2
print(ans % (10 ** 9 + 7))

Solution (Python):
n, k = input().split()
n = int(n)
k = int(k)
A = [int(a) for a in input().split()]
m = 1000000007
inv = 0

count = 0

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

ans = inv*k + inv2*sum(range(k))

ans %= m
print(ans)

Solution (Python):

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

n_cnt = [0 for _ in range(2001)]
less = [0 for _ in range(2001)]
ress = [0 for _ in range(n)]
for i in a:
    n_cnt[i] += 1

tmp = 0
for i, c in enumerate(n_cnt):
    less[i] += tmp
    tmp += c

for i in range(n):
    cnt = 0
    tgt = a[i]
    for j in a[i+1::]:
        cnt += 1 if j < tgt else 0
    ress[i] = cnt


cnt = 0
for _a, less_r in zip(a, ress):
    less_all = less[_a]
    cnt +=  ((k*(k-1))//2) * less_all + less_r * k

print(cnt%1000000007)

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

right = []

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


miman = [0 for i in range(2002)]

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




ans=0
for i in range(n):
    ans += (right[i]*k)%mod
    ans += (miman[a[i]]*(k-1)*k//2)%mod
    ans %= mod
        
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7


def LI():
    return list(map(int, sys.stdin.readline().split()))


def II():
    return int(sys.stdin.readline())


def LS():
    return list(map(list, sys.stdin.readline().split()))


def S():
    return sys.stdin.readline()[:-1]


def main():
    n, k = LI()
    a_s = LI()
    ts = [0 for i in range(n)]
    f_ts = [0 for i in range(n)]
    for i in range(n):
        for j in range(n):
            if a_s[j] < a_s[i]:
                ts[i] += 1
                if j > i:
                    f_ts[i] += 1
    sum_f = sum(f_ts)
    sum_ = sum(ts)
    if (k - 1) % 2 == 0:
        ans = (sum_f + int(sum_ * (k - 1) / 2)) % MOD
        print(int(ans) % MOD * k % MOD)
    else:
        ans = 2 * sum_f + sum_ * (k - 1) % MOD
        print(int(ans) % MOD * int(k / 2) % MOD)


if __name__ == "__main__":
    main()

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

N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
bit = Bit(2000)
ans = 0
hist = [0] * 3
for i in range(min(K, 3)):
    for j in range(N):
        ans = ans + i*N + j - bit.sum(A[j])
        bit.add(A[j], 1)
    hist[i] = ans
if K <= 3:
    print(ans)
else:
    ans = hist[0]
    a = (hist[1] - hist[0])
    d = (hist[2] - hist[1]) - (hist[1] - hist[0])
    ans = ans + (K-1) * (2*a + (K-2)*d) // 2
    print(int(ans % (1000000007)))

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()]

inv_t = [0]+[1]
for i in range(2,5):
  inv_t += [inv_t[MOD % i] * (MOD - int(MOD / i)) % MOD]

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)) % MOD)) * inv_t[2]

    cnt2 = (cnt2 * tmp) % MOD

cnt = (cnt + cnt2) % MOD

print(int(cnt))

Solution (Python):
from decimal import *
n, k = map(int,input().split())
a = list(map(int,input().split()))
inner = 0
outer = 0
for i in range(0,n):
    for j in range(0,n):
        if a[i] > a[j]:
            outer += 1
            if i < j:
                inner += 1

print((Decimal(((inner) * (k)) + Decimal((outer) * Decimal((k) * (k-1)) / 2))%(1000000007)))

Solution (Python):
N,K = map(int,input().split())
A =list(map(int,input().split()))
pre_a = A[0]
ans =0
def sum(n):
    if n%2==0:
        return  (1+n)*(n//2)
    else:
        return  (1+n)*(n//2)+(n//2+1)

sumk = sum(K)
sumk1 = sum(K-1)
for i,a in enumerate(A):
    counter =0
    for b in A[i+1:]:
        if a > b:
            counter += 1

    ans += counter*sumk
    back = 0
    for c in A[:i]:
        if c < a:
            back += 1
    
    ans += back*sumk1
print(ans%(10**9+7))

Solution (Python):
n, k = map(int, input().strip().split(' '))
a = list(map(str, input().strip().split(' ')))
MOD = 1000000007

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

bm = 0
for i in range(n):
  for j in range(n):
    if int(a[i]) > int(a[j]):
      bm = bm + 1
if k % 2 == 0:
  bm = (bm % MOD) * ((k // 2) % MOD) * (k-1 % MOD)
else:
  bm = (bm % MOD) * (k % MOD) * (((k-1) // 2) % MOD)
s = (bn % MOD) * (k % MOD) + (bm % MOD)
print(s % MOD)

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
for v in A:
    i = g[v]
    ans += S * (N - i)

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

Solution (Python):
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N, K = MAP()
    A = LIST()
    count = 0
    if K % 2 == 0:
        tmp1 = int(K / 2)
        tmp2 = K - 1
    else:
        tmp1 = K
        tmp2 = int((K - 1) / 2)
    for i in range(N):
        count_all = 0
        count_ = 0
        for j in range(N):
            if A[i] > A[j]:
                count_all += 1
                if i < j:
                    count_ += 1
        count += count_ * K % mod
        count += (((tmp1 * tmp2) % mod) * count_all) % mod
        count = count % mod
        
    print(int(count) % mod)

if __name__ == '__main__':
    main()

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


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


ans2 = 0
B = sorted(A)
now = B[0]
cnt = 0
for i in range(1,N):
    if now != B[i]:
        cnt = i
        ans2 += cnt
        now = B[i]
    else:
        ans2 += cnt

ans11 = ans1 * K
ans22 = ans2 * (K * (K-1) // 2)
ans = ans11 + ans22
print(ans % MOD)

Solution (Python):
import sys
inputs = sys.stdin.readlines()

from itertools import cycle
N, K = map(int, inputs[0].split())
A = list(map(int, inputs[1].split()))
B_ = A + A
MOD = 10 ** 9 + 7

N, K
list(A+A)

counts = [0, 0]
for i in range(N):
    for j in range(i, N):
        if B_[i] > B_[j]:
            counts[0] += 1
for s in range(1, N):
    for i in range(N-s):
        if B_[i+s] > B_[N-1+s]:
            counts[1] += 1
print((counts[0] * K*(K+1)//2 + counts[1] * K*(K-1)//2) % MOD)

Solution (Python):
import copy


def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A) - 1, i, -1):
            if A[j] < A[j - 1]:
                A[j], A[j - 1] = A[j - 1], A[j]
                cnt += 1
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
b = copy.deepcopy(a)
tmp = [0] * n
initial = bubble_sort(a)
ans = initial
for i in range(n):
    cnt = 0
    for j in b:
        if b[i] > j:
            cnt += 1
    tmp[i] = cnt
d = sum(tmp)
ans = k * (2 * initial + d * (k - 1)) // 2
print(ans % (10 ** 9 + 7))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 1000000007
num = 0;
for i in range(N):
    Bi = A[i]
    n1 = 0
    for j in range(i):
        Bj = A[j]
        if(Bi > Bj):
            n1 += 1
    num += (K*(K-1)*n1//2)%MOD
    n2 = 0
    for j in range(i+1, N):
        Bj = A[j];
        if(Bi > Bj):
            n2 += 1;
    num += (K*(K+1)*n2//2)%MOD
print(num%MOD)

Solution (Python):
import sys

input = sys.stdin.readline
sys.setrecursionlimit(1000000)


def getN():
    return int(input())


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


import math
MOD = 10 ** 9 + 7

n, k = getList()
anums = getList()

space = [[] for i in range(2002)]
remain = [1 for j in range(n)]
yet = n

for i, x in enumerate(anums):
    space[x].append(i)


ans = 0
for s in space:
    if s:
        jump = 0
        ls = len(s)
        yet -= ls
        for num in s:
            jump += sum(remain[:num])
            remain[num] = 0
            
        ans += ls * (yet * (k * (k-1))) // 2
        ans += jump * k
        
        

        ans %= MOD
        
        
print(ans)

Solution (Python):
import copy
import sys

input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = copy.deepcopy(a)

cnta = 0
cntc = 0

w = 10 ** 9 + 7

e = [0] * len(a)

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

            e[i] += 1


f = [0] * len(b)
for i in range(len(b)):
    for j in range(len(b)):
        if b[i] > b[j]:
            f[i] += 1


wa = (k*(k - 1)//2) * sum(f)  + sum(e) * k
print(wa % w)

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

mod = 10 ** 9 + 7
ans = 0

if K == 1:
    for i in range(N-1):
        for j in range(i+1, N):
            if A[i] > A[j]:
                ans += 1
        ans %= mod
    print(ans)
    exit()


for i in range(N):
    tmp = 0
    for j in range(i+1, N):
        if A[i] > A[j]:
            tmp += ((K * (K+1) // 2) % mod)
    for j in range(i):
        if A[i] > A[j]:
            tmp += ((K * (K-1) // 2) % mod)
    tmp %= mod
    ans += tmp

print(ans % mod)

Solution (Python):
cnt=[]
before=[]
MOD=1000000007
n,k=map(int,input().split())
arr=list(map(int,input().split()))

for i in range(0,3010):
    cnt.append(0);
    before.append(0);

for i in range(n):
    count=0
    count1=0
    for j in range(i+1,n):
        if(arr[i]>arr[j]):
            cnt[i]+=1


for i in range(n):
    for t in range(0,i):
        if(arr[i]>arr[t]):
            before[i]+=1


sum=0
sum1=0
for i in range(n):
    x=(k*(k+1))//2
    y=cnt[i]*x
    sum=sum+y
    a=(k*(k-1))//2
    b=before[i]*a
    sum1=sum1+b
c=sum+sum1
print((c)%MOD)

Solution (Python):
import sys
from pprint import pprint

def solve(n, k, a):
    aa = a + a
    tr_n_a = 0
    for i in range(0, n-1):
        for j in range(i+1, n):
            if a[i] > a[j]:
                tr_n_a += 1
    

    tr_n = 0
    s_a = sorted(a, reverse=True)
    for i in range(0, n-1):
        for j in range(i+1, n):
            if s_a[i] > s_a[j]:
                tr_n += 1
    

    if tr_n == 0:
        print(0)
    else:
        print((tr_n * k * (k - 1) // 2 + tr_n_a * k) % (10**9 + 7))

if __name__ == '__main__':
  n, k = map(int, sys.stdin.readline().strip().split(" "))
  a = list(map(int, sys.stdin.readline().strip().split(" ")))
  solve(n, k, a)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)

from math import factorial
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=10**9+7

def combi(m, r):
    if m - r < r: r = m - r
    if r == 0: return 1
    if r == 1: return m

    nume = [m - r + j + 1 for j in range(r)]
    deno = [j + 1 for j in range(r)]

    for l in range(2,r+1):
        pivot = deno[l - 1]
        if pivot > 1:
            offset = (m - r) % l
            for j in range(l-1,r,l):
                nume[j - offset] /= pivot
                deno[j] /= pivot

    result = 1
    for l in range(r):
        if nume[l] > 1:
            result *= int(nume[l])

    return result

cnt=0
cnt2=0
if n==1:
    print("0")
else:
    for i in range(n-1):
        for j in range(i+1,n):
            if a[i]>a[j]:
                cnt+=1
    if k==1:
        coef=1
    else:
        for i in range(n-1):
            for j in range(i+1,n):
                if a[i] < a[j]:
                    cnt2+=1
        coef=combi(k,2)
    print(int((coef*(cnt+cnt2)+cnt*k) % p))

Solution (Python):
from collections import defaultdict

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    A2 = A + A
    d2 = defaultdict(int)
    for i in range(2*N):
        for j in range(i,2*N):
            if A2[i] > A2[j]:
                d2[A2[i]] += 1

    d = defaultdict(int)
    for i in range(N):
        for j in range(i,N):
            if A[i] > A[j]:
                d2[A2[i]] -= 1
                d[A[i]] += 1
    ans = 0

    for key,value in d2.items():
        ans += (K * ((2 * d[key] + (K - 1) * (value - d[key])))) // 2
        
    print(int(ans) % MOD)

main()

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

print(c)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
a2 = a + a
def tentou (l):
    count = [0]*len(l)
    for i in range(len(l)-1):
        for j in range(i+1,len(l)):
            if l[i] > l[j]:
                count[i] += 1
    return count
if n == 1:
    print(0)
else:
    a_v = tentou(a)
    a2_v = tentou(a2)
    mergin = [x-y-y for (x,y) in zip(a2_v,a_v)]
    if k == 1:
        S = sum(a_v)
        result = S % ((10**9) + 7)
    else:
        for i in range(len(a_v)):
            a_v[i] = a_v[i]*(k*(k+1))//2 + mergin[i]*(k*(k-1))//2
        S = sum(a_v)
        result = S % ((10**9) + 7)
        print(result)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt

N, K = MAP()
A = LIST()

B = []
for i in range(2):
    for a in A:
        B.append(a)

tenchi1 = bubble_sort(A)
tenchi2 = bubble_sort(B)

ni = tenchi2-2*tenchi1





wa2 =  (K) * (K-1) // 2







ans1 = K*tenchi1
ans2 = wa2 * ni
ans = ans1 + ans2

ans = ans % mod
print(ans)

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

    k2 = k**2-((k**2-k)//2)

    o = [0]*n
    for i in range(n):
        a1 = a[:i]
        a2 = a[i+1:]
        a1 = len([j for j in a1 if j < a[i]]) * (k2-k)
        a2 = len([j for j in a2 if j < a[i]]) * (k2)
        o[i] = a1+a2
    print(sum(o)%(10**9+7))

if __name__ == "__main__":
    f_b()

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

Solution (Python):
from decimal import *
N, K = map(int, input().split())
As = list(map(int, input().split()))
MOD = 10**9 + 7


K_1 = Decimal(K)*Decimal(1+K) / Decimal(2)
K_2 = (K_1 - Decimal(K)) % Decimal(MOD)
K_1 %= Decimal(MOD)

res_next = [0 for i in range(N)]
for i in range(N):
    a = As[i]
    for j in range(i+1, N):
        if a > As[j]:
            res_next[i] += 1

res_prev = [0 for i in range(N)]

for i in range(N):
    a = As[i]
    for j in range(i):
        if a > As[j]:
            res_prev[i] += 1

ans = Decimal(0)

for i in range(N):
    ans += (Decimal(res_next[i]) * K_1) % Decimal(MOD)
    ans %= Decimal(MOD)
    ans += (Decimal(res_prev[i]) * K_2) % Decimal(MOD)
    ans %= Decimal(MOD)

print(int(ans))

Solution (Python):
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
ans = 0
a_2_list = a_list * 2
sorted_a = sorted(a_list, reverse=True)

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

for i in range(n):
  indexes = [j for j, x in enumerate(sorted_a) if x == a_list[i]]
  ans += (n-indexes[-1]-1) * k*(k-1)//2%(10**9+7)

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

Solution (Python):


import sys
from functools import reduce

X = 10 ** 9 + 7

def main() -> int:
    ls = sys.stdin.read().splitlines()
    [n, k] = [int(x) for x in ls[0].split(' ')]
    xs = [int(x) for x in ls[1].split(' ')]
    first = [len([x for x in xs[:i] if x > xs[i]]) for i in range(n)]
    xsxs = xs * 2
    ds = [
            len([x for x in xsxs[:i] if x > xsxs[i]]) - first[i - n]
            for i in range(n, 2 * n)]
    ss = [k * (2 * first[i] + (k - 1) * ds[i]) // 2 for i in range(n)]
    print(sum(ss) % X)
    return 0


if __name__ == "__main__":
    exit(main())

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
inf=10**9+7
now=0
cnt=[0]*n
cntlast=0
plus=0
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            if i<j:
                cnt[j]+=1
            plus+=1
print((k*sum(cnt)+plus*(k-1)*k//2)%inf)

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

count = 0
for index, i in enumerate(a):
    for j in a[index+1:]:
        if i > j:
            count += k * (k + 1) // 2
        elif i < j:
            count += (k - 1) * k // 2

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

Solution (Python):
import numpy as np

MOD = 1000000007

def count_inv2(a):
    count = 0
    prev = a[a.shape[0] - 1]
    m = 1
    for j in range(a.shape[0] - 2, -1, -1):
        if prev > a[j]:
            count += m * (j + 1)
            prev = a[j]
            m = 1
        else:
            m += 1
    return count


def count_inv(a):
    count = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] > a[j]:
                count += 1
    return count


stdin = open(0, 'rb')
N, K = map(int, stdin.readline().split())
A = np.fromstring(stdin.readline(), dtype=np.int64, sep=' ')
x = count_inv(A)
y = count_inv2(np.sort(A))
ans = (K * x + K*(K - 1) // 2 * y) % MOD
print(ans)

Solution (Python):
n,k =map(int,input().split())
A =list(map(int,input().split()))
plus=[0]*(n)
C=[0]*2001
for i in range(n):
	for j in range(A[i]):
		C[j]+=1

	plus[i]=C[A[i]]
count=0
for i in range(n):
	count+=plus[i]*(k)
	
	count+=C[A[i]]*k*(k-1)//2
	count=count%(10**9+7)



print(count)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
Mod=10**9+7
ans_first=0
ans_sec=0
for i in range(len(A)-1):
  for j in range(i,len(A)):
    if A[i]>A[j]:
      ans_first+=1
for i in A:
  for j in A:
    if i > j:
      ans_sec+=1
if K%2==0:
  tmp=(2*ans_first+(K-1)*ans_sec)%Mod
  K=K//2
  ans=(tmp*K)%Mod
else:
  tmp=(ans_first+(K-1)//2*ans_sec)%Mod
  ans=(tmp*K)%Mod
print(ans)

Solution (Python):
N,K=map(int,input().split())
A = list(map(int,input().split()))
MOD = 1000000007
cnt = 0
for i in range(N-1):
  for j in range(i+1,N):
    if ( A[i] > A[j] ):
      cnt += 1

AS = sorted(A, reverse=True)
sumn = 0
tmp = 0
for i in range(1,N):
  if AS[i] != AS[i-1]:
    tmp = i
  sumn += tmp


if K%2==0:
  mulk = K * ((K-1)//2) + (K//2)
else:
  mulk = K * ((K-1)//2)
mulk %= MOD 

print ( ((cnt * K)%MOD  + (sumn * mulk) % MOD) %MOD)

Solution (Python):
def p_b():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    ans = 0

    l = []
    r = []
    for i in range(N):
        lc = 0
        rc = 0
        for j in range(N):
            if A[i] > A[j]:
                if i > j:
                    lc += 1
                else:
                    rc += 1
        l.append(lc)
        r.append(rc)
        
    an = K * (K + 1) // 2 % mod
    for i in range(N):
        sum_r = an * r[i]
        sum_l = (an - K) * l[i]
        ans += sum_r + sum_l
        ans %= mod
	
    print(ans)


if __name__ == '__main__':
    p_b()

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
C=0
for t in range(n):
  for T in range(n):
    if a[t]>a[T]:
      C+=1
      C%=(10**9+7)
      
w=len(list(set(a)))


if w==1:
  print(0)
  exit()

if k>=2:
  e=((k*(k-1))//2)%(10**9+7)
elif k==1:
  e=1

ans+=(C*e)%(10**9+7)

count=0
for i in range(n):
  for j in range(n):
    if i<j:
      if a[i]>a[j]:
        count+=1
        count%=(10**9+7)
k%=10**9+7
ans+=(count*k)%(10**9+7)

ans%=10**9+7

print(ans)

Solution (Python):
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
kk=k-1

cnt=0
res=0
for i in range(n):
    cnt=0
    rev=0

    for j in range(i+1,n):
        if a[i]>a[j]:
            cnt+=1
        if a[i]<a[j]:
            rev+=1
    res+=rev*((kk+1)*kk)//2
    res+=cnt*((k+1)*k)//2
    res%=mod

print(res)