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):
n,k = map(int,input().split())
a = list(map(int,input().split()))
dp1 = [0 for _ in range(n)]
dp2 = [0 for _ in range(n)]
mod = 10**9+7
for i in range(n):
    for j in range(n):
        if a[j]>a[i]:
            dp1[i]+=1
            if i>j:
                dp2[i]+=1
ans = 0
for i in range(n):
    ans += ((k-1)*dp1[i]+dp2[i]*2)*k//2
    ans %= mod
print(ans)

Solution (Python):
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
import bisect
mod=10**9+7
AA=[]
ans1=0
for i in range(n):
  ans1+=i-bisect.bisect_right(AA,A[i])
  AA.append(A[i])
  AA.sort()
ans2=0
for i in range(n-1):
  ans2+=n-bisect.bisect_right(AA,AA[i])

ans=(ans1*k)%mod
ans=(ans+ans2*k*(k-1)//2)%mod
print(ans)

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

X = [0]*N
Y = [0]*N

for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            X[i] += 1
        elif A[i] < A[j]:
            Y[j] += 1

mod = 10**9+7
ans = 0
for i in range(N):
    ans += K*(K+1)*X[i]//2%mod
    ans += (K-1)*K*Y[i]//2%mod
print(ans%mod)

Solution (Python):
MOD = 10**9 + 7
N,K = map(int,input().split())
A = list(map(int,input().split()))
cnt = [0 for i in range(2001)]
for a in A:
	cnt[a] += 1
total = [0]
for i in range(2000):
	total.append(total[i] + cnt[i+1])

base = 0
loop = 0
keisu = K*(K-1)//2 % MOD
for i in range(N):
	a = A[i]
	for j in range(i+1, N):
		if a > A[j]:
			base += 1
	loop = (loop + total[a-1] * keisu) % MOD

print((base*K + loop) % MOD)

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, k = li()
a = list(li())
MOD = 10**9 + 7

ans = 0
for i, ai in enumerate(a):
    for j, aj in enumerate(a):
        if ai > aj:
            if j < i:
                ans += ((k-1)*k // 2)
            else:
                ans += ((k+1)*k // 2)

            ans %= MOD


print(ans % MOD)

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

mod = 10**9 + 7
nums = [[0, 0] for _ in range(n)]

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

kbig = ((k+1) * k) // 2
ksmall = (k * (k-1)) // 2

result = 0
for i in range(n):
    result = (result + nums[i][0] * ksmall + nums[i][1] * kbig) % mod

print(result)

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

R = {}
L = []
for i in A:
  if i not in R:
    R[i] = 1
    L.append(i)
  else:
    R[i] += 1

L.sort(reverse = True)

k = 0
t = R[L[0]]
for i in range(1, len(L)):
  k = (k + t * R[L[i]]) % MOD
  t += R[L[i]]

ans = k * ((K * (K - 1)) // 2) % MOD

k = 0
for i in range(N):
  for j in range(i):
    if A[i] < A[j]:
      k += 1
ans = (ans + k * K) % MOD

print(ans)

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

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

A_sorted = sorted(A)
smaller = [0] * N
for i in range(1, N):
    if A_sorted[i - 1] < A_sorted[i]:
        smaller[i] = i
    else:
        smaller[i] = smaller[i-1]
sum_smaller = sum(smaller)

ans = (((tentou * K) % mod) + ((sum_smaller * (((K * (K - 1)) // 2) % mod)) % mod)) % mod
print(ans)

Solution (Python):

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

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

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

total = 0
for i in range(N):
	total += K * bigger_after[i]
	total += K * (K - 1) * bigger[i] //2
	total = total % 1000000007
print(total)

Solution (Python):
I=lambda:input()
L=lambda:list(map(int,I().split()))
n,k=L()
a=L()
m=10**9+7
kk=(k*(k+1)//2)%m
k=(k*(k-1)//2)%m
from bisect import bisect_left
x=0
for i in range(n):
  if i!=0:
    l=a[:i]
    l.sort()
    b=bisect_left(l,a[i])
    x+=(b*k)%m
  if i!=n-1:
    l=a[i+1:]
    l.sort()
    b=bisect_left(l,a[i])
    x+=(b*kk)%m
  x%=m
print(x)

Solution (Python):
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
INF=10**9+7
a_list=list(map(int,input().split()))
count=0
ans=0
for i in range(n):
    for j in range(i+1,n):
        if a_list[i]>a_list[j]:
            count+=1
ans=(count*k)%INF
m=max(a_list)
D=[0]*m
for i in a_list:
    D[i-1]+=1
count=0
Sum=D[m-1]
for i in range(m-2,-1,-1):
    count=(count+Sum*D[i])%INF
    Sum=(Sum+D[i])%INF
count=(count*k*(k-1)//2)%INF
ans=(ans+count)%INF
print(ans)

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


def tentousu(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


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


print((tentousu(a_) * k + chiisai(a_) * k * (k - 1) // 2) % (10 ** 9 + 7))

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

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

    ans = (((front * K * (K + 1) // 2) % MOD) + ((back * (K - 1) * K // 2) % MOD)) % MOD
    print(ans)


sol()

Solution (Python):
from collections import defaultdict
mod = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))

d1 = defaultdict(lambda:0)
d2 = defaultdict(lambda:0)

for i in range(N):
    for j in range(N):
        if A[i]>A[j]:
            if i<j:
                d1[i]+=1
            d2[i]+=1

ans = 0
for i in range(N):
    ans += (K*(K-1))//2%mod*d2[i]+K*d1[i]
    ans %= mod

print(ans)

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

print((ans*k*(k+1)//2+anst*(k-1)*k//2)%mod)

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

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

def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    ans = 0

    for i in range(N):
        a = A[i]
        al = 0
        after = 0
        for i in range(i):
            if A[i] < a:
                al += 1
        for i in range(i+1, N):
            if A[i] < a:
                al += 1
                after += 1
        ans += K*(K-1)//2*al%Q + after*K%Q
        ans %= Q
    print(ans)
    
if __name__ == '__main__':
    main()

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

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

y=[0 for _ in range(n)]
for i in range(1,n):
	for j in range(i):
		if a[j]<a[i]:
			y[i]+=1


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

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

count_bf = [0] * n
count_af = [0] * n

for i in range(n):
    for j in range(n):
        if j < i:
            if lst[i] > lst[j]:
                count_bf[i] += 1
        if j > i:
            if lst[i] > lst[j]:
                count_af[i] += 1
                
res = 0
for i in count_af:
    res += ((k * (k+1) // 2) * i) % (10**9 + 7)
for i in count_bf:
    res += ((k * (k-1) // 2) * i) % (10**9 + 7)
print(res % (10**9 + 7))

Solution (Python):

N,K = map(int,input().split())
A = list(map(int,input().split()))
count = 0
for i,a in enumerate(A):
    for j,b in enumerate(A):
        if a > b:
            if i < j:
                count+=(K*(K+1))//2
            else:
                count+=(K*(K-1))//2
                
print(count%1000000007)

Solution (Python):
import collections

MOD = 10**9+7


def solve(n, k, a):
    total = 0

    cnt = [0] * 2001
    for v in a:
        cnt[v] += 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if a[i] > a[j]:
                total += 1
    total *= k
    l_sum = [0] * 2001
    r_sum = [0] * 2001
    for i in range(1, 2001):
        l_sum[i] = l_sum[i-1] + cnt[i-1]
    for i in range(1999, 0, -1):
        r_sum[i] = r_sum[i + 1] + cnt[i + 1]
    z = k*(k-1)//2
    for i in range(1, 2001):
        total += z*(l_sum[i]) * cnt[i]

    return total % MOD


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve(n, k, a))


if __name__ == "__main__":
    main()

Solution (Python):
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


MOD = int(1e9) + 7

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

init = 0
total = 0
for i in range(N):
    for j in range(i+1, N):
        if A[i] > A[j]:
            init += 1
        if A[i] != A[j]:
            total += 1
            
ans = init * K
ans %= MOD

hoge = (K * (K - 1)) // 2
hoge %= MOD
ans += total * hoge
ans %= MOD

print(ans)

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

print(ans)

Solution (Python):


import sys

class BKleeneInversion:
    def solve(self):
        MOD = 10 ** 9 + 7

        n, k = [int(_) for _ in input().split()]
        a = [int(_) for _ in input().split()]
        s = [0] * n
        t = [0] * n
        for i in range(n):
            for j in range(i):
                if a[j] < a[i]:
                    t[i] += 1
            for j in range(i + 1, n):
                if a[j] < a[i]:
                    s[i] += 1
                    t[i] += 1

        

        ans = k * sum(s) + k ** 2 * sum(t) - (k * (k + 1)) * sum(t) // 2
        ans %= MOD
        print(ans)

solver = BKleeneInversion()
input = sys.stdin.readline

solver.solve()

Solution (Python):



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

    def sum(self, i): 
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def range(self,l,r): 
        return sum(r) - sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= n:
            self.tree[i] += x
            i += i & -i
        
    
     

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 
 

n,k = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]
 
sA = sorted(a)


 
b = BIT(n)
 
from bisect import *
res = [0]*n
for i,ai in enumerate(a):
    j = bisect_left(sA, ai)
    res[i] = i - b.sum(j)
    b.add(j,1)
 


MOD = 10**9 + 7
ans = 0
for i,ai in enumerate(a):
    ans += k*res[i]
    ans %= MOD
    j = bisect_left(sA, ai)
    ans += (k*(k-1)//2%MOD)*(n - b.sum(j))
    ans %= MOD
    

print(ans)

Solution (Python):
N, K = map(int, input().split())
As = list(map(int, input().split()))
r = 0
for i in range(N):
  A = As[i]
  a = len(list(filter(lambda A2: A2 < A, As[:i])))
  b = len(list(filter(lambda A2: A2 < A, As[i+1:])))
  
  r = (r+a*(K-1)*K//2)%1000000007
  r = (r+b*(K+1)*K//2)%1000000007
print(r)

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

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

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

A.extend(A)

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

print(((K * (K - 1) // 2) * b + K * a) % (10**9 + 7))

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

class Bit(object):
    def __init__(self):
        self.bit = [0] * 2001

    def add(self, i):
        while i <= 2000 and i >= 1:
            self.bit[i] += 1
            i += i & -i

    def query(self, i):
        ans = 0
        while i <= 2000 and i >= 1:
            ans += self.bit[i]
            i -= i & -i
        return ans

gl, suf = Bit(), Bit()

for i in range(n):
    gl.add(a[i])

ans = 0

for i in range(n - 1, -1, -1):
    u = suf.query(a[i] - 1)
    v = gl.query(a[i] - 1)
    ans += (u + (u + v * (k - 1))) * k // 2
    suf.add(a[i])

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

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

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

ans = 0
S = [0]*N
T = [0]*N
for i, a in enumerate(A):
    for j, a_ in enumerate(A):
        if a_<a: S[i]+=1
        if j>i and a_<a: T[i]+=1

print((K*(K-1)//2*sum(S) + sum(T)*K)%(10**9+7))

Solution (Python):



def ri():
    return int(input())

def rl():
    return list(input().split())

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

MOD = 10**9+7

def main():
    n, k = rli()
    la = rli()
    rev1 = 0
    rev2 = 0
    for i in range(len(la)):
        for j in range(len(la)):
            if la[i] > la[j]:
                if i < j:
                    rev1 += 1
                else:
                    rev2 += 1
    ans = rev1 * k*(k+1)//2 + rev2 * (k-1)*k//2
    ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
mod = 10**9+7
cnt = 0
for ind,a in enumerate(A):
    cnt_l = 0
    cnt_r = 0
    for ind2,b in enumerate(A):
        if(ind==ind2):
            continue
        if(ind<ind2):
            if(a>b):
                cnt_r += 1
        if(ind>ind2):
            if(a>b):
                cnt_l += 1
    cnt += cnt_r*(K*(K+1)//2)
    cnt += cnt_l*((K-1)*K//2)
    cnt %= mod
print(cnt)

Solution (Python):
mod = 10**9+7
n,k = map(int, input().split())
a = list(map(int, input().split()))
b = [0]*2001
for i in a:
    b[i] += 1
for i in range(2000):
    b[i+1] += b[i]

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

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    m,d = LI()
    ans = 0
    for i in range(1,m+1):
        for j in range(1,d+1):
            d1 = j%10
            d2 = j//10
            if d1 >= 2 and d2 >= 2 and d1*d2 == i:
                ans += 1
    print(ans)
    return


def B():
    def add(i):
        while i <= m:
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n,k = LI()
    m = 2000
    a = LI()
    bit = [0]*(m+1)
    ans = 0
    for i in range(n):
        ans += (i-sum(a[i]))*k
        add(a[i])
    inv = pow(2,mod-2,mod)
    for i in range(n):
        ans += sum(a[i]-1)*k*(k-1)*inv%mod
    print(ans%mod)
    return


def C():
    n = I()

    return


def D():

    return


def E():

    return


def F():

    return


if __name__ == "__main__":
    B()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

MOD = 10**9 + 7

N,K = map(int,input().split())
A = np.array(input().split(), dtype=np.int64)


def type_1():
    bl1 = A[:,None] > A[None,:]
    bl2 = np.arange(N,dtype=np.int64)[:,None] < np.arange(N,dtype=np.int64)[None,:]
    x = ((bl1 & bl2)*1).astype(np.int64).sum() % MOD
    return x*K%MOD

def type_2():
    
    counter = np.bincount(A)
    cum = counter.cumsum()
    larger = N-cum
    x = (larger * counter % MOD).sum() % MOD
    y = K*(K-1)//2 % MOD
    return x*y%MOD

answer = (type_1() + type_2()) % MOD
print(answer)

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))
tentou = []
tentou_all = []
for i in range(N):
    now = a[i]
    count = 0
    for j in range(i+1, N):
        if now > a[j]:
            count += 1
    tentou.append(count)

for i in range(N):
    now = a[i]
    count = 0
    for j in range(N):
        if now > a[j]:
            count += 1
    tentou_all.append(count)

ans = 0
for i in range(N):
    x = tentou[i] + tentou_all[i]*(K-1)
    y = tentou[i]
    ans += (K*(x+y))//2
    ans %= 1000000007

print(ans)

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

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

print(ans)

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

ans = 0

for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            if i<j:
                ans += k*(k+1)//2
            else:
                ans += (k-1)*k//2
            ans %=10**9+7
print(ans)

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

print((a*K+b*K*(K-1)//2)%P)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,K = inpl()
aa = inpl()
cnts = [0]*2005

izyos = [0]*N

for i,a in enumerate(aa):
    izyos[i] = sum(cnts[a+1:])
    cnts[a] += 1

sums = [0]*N
for i,a in enumerate(aa):
    sums[i] = sum(cnts[a+1:])

ans = sum(izyos)*K+sum(sums)*((K-1)*K//2)%mod
ans %= mod
print(ans)

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

MOD = 10**9 + 7

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

    ans += x * k * (k + 1) // 2
    ans %= MOD
    ans += y * (k-1) * k // 2
    ans %= MOD
    

print(ans)

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

Solution (Python):

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  

def solve(N: int, K: int, A: "List[int]"):
    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
            tmp = 0
            if A[i] > A[j]:
                tmp = K * (K + 1) // 2
            elif A[i] < A[j]:
                tmp = (K - 1) * K // 2
            ret += tmp
            ret %= MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(N-1-0+1) ]  
    solve(N, K, A)

if __name__ == '__main__':
    main()

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def s_list(): return list(input())
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]

n, k = wi()
a = wi()

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

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):
def main():
    import sys
    input = sys.stdin.readline
    
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            if arr[j] < arr[i]:
                ans += k
        for j in range(n):
            if arr[j] < arr[i]:
                ans += (k * (k - 1) >> 1) % 1000000007
        ans %= 1000000007
    print(ans % 1000000007)
    
    return 0

main()

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

ans = 0
for i, ai in enumerate(a):
    left = 0
    right = 0
    for j in range(i):
        if ai > a[j]:
            left += 1
    for j in range(i + 1, n):
        if ai > a[j]:
            right += 1
    ans += (k * (k + 1) * right // 2) + (k * (k - 1) * left // 2)
print(ans % 1000000007)

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



N,K = II()
A = III()

r = [0]*N
l = [0]*N

for i in range(N):
    for j in range(i+1,N):
        if A[j]<A[i]:
            r[i] += 1
    for j in range(i):
        if A[j]<A[i]:
            l[i] += 1

ans = 0

for i in range(N):
    ans += r[i]*K*(K+1)//2
    ans %= mod
    ans += l[i]*(K-1)*K//2
    ans %= mod

print(ans)