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=[int(i) for i in input().split()]
mod=10**9+7
import math
import bisect

n_max=2000
nn=int(math.log2(n_max))+1
BIT=[0]*(2**nn)
BIT.insert(0,0)

def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=n_max:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

ans1=0
for i in range(n):
  ans1+=i-bitsum(BIT,A[i])
  bitadd(BIT,A[i],1)

ans2=0
A.sort()
for i in range(n-1):
  ans2+=n-bisect.bisect_right(A,A[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()))
ans = 0
time_ans = 0
A_sort = sorted(A)
before = -1
b = -1
for i in range(N):
        a_sorti = A_sort[i]
        if a_sorti == before:
                time_ans += b
                continue
        b = A_sort.index(a_sorti)
        time_ans += b
        before = a_sorti

for i in range(N - 1):
        for j in range(i + 1,N):
                if A[i] > A[j]:
                        ans += 1
ans1 = K * (K + 1) * time_ans // 2 - (time_ans - ans) * K
print(ans1 % (10 ** 9 + 7))

Solution (Python):
from bisect import bisect_left as lower_bound, bisect_right as upper_bound

mod = 10**9 + 7

def inversion_count(arr, n, k):
	b = []
	cnt = 0
	for i in range(n-1, -1, -1):
		pos = lower_bound(b, arr[i])
		cnt = (cnt + pos)%mod
		b.insert(pos, arr[i])
	
	cnt = (cnt*k)%mod	
	
	for i in range(n):
		pos = lower_bound(b, arr[i])

		cnt = (cnt + ((k*(k-1))//2)*pos)%mod

	
	return cnt



def main():
	n,k = list(map(int, input().strip().split()))

	arr = list(map(int, input().strip().split()))

	print (inversion_count(arr, n, k))

if __name__ == "__main__":
	main()

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

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

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

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

bit = Bit(2000)

intra, inter = 0, 0
for i, a in enumerate(map(int, input().split())):
    bit.add(a, 1)
    intra += i + 1 - bit.sum(a)
    inter += bit.sum(a - 1)

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

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

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

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

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

bit = Bit(2000)

intra, inter = 0, 0
for i, a in enumerate(map(int, input().split())):
    bit.add(a, 1)
    intra += i + 1 - bit.sum(a)
    inter += bit.sum(a - 1)

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

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

tentosu_f = 0
tentosu_l = 0
mod = 10**9 + 7
ans = 0

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

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

ten_f = 0
ten_l = 0

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

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

ans = (ten_f * (K)) + ((K * ((K - 1)) // 2) * ten_l)
print(ans % mod)

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

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

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

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

bit = Bit(2000)

intra, inter = 0, 0
for i, a in enumerate(A):
    bit.add(a, 1)
    intra += i + 1 - bit.sum(a)
    inter += bit.sum(a - 1)

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

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

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

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

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









bit = Bit(2000)

intra = 0
inter = 0
for i in range(len(A)):
    a = A[i]
    bit.add(a, 1)
    intra += i + 1 - bit.sum(a)
    if a != 1:
        inter += bit.sum(a - 1)








mod = 10**9 + 7

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

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

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

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

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

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

bit = Bit(2000)

intra = 0
for i in range(len(A)):
    a = A[i]
    bit.add(a, 1)
    intra += i + 1 - bit.sum(a)



mod = 10**9 + 7

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

Solution (Python):
N, K = map(int,input().split())
An = list(map(int,input().split()))
f_count = 0
r_count = 0

for i in range(N):
    for j in range(N):
        if i < j:
            if An[i] < An[j]:
                f_count += 1
            elif An[i] > An[j]:
                r_count += 1

Ans = (f_count * K*(K-1)//2 + r_count * (K*(K+1)//2)) % (10**9+7)

print(int(Ans))

Solution (Python):
import collections

N,K = map(int, input().split())
arr = list(map(int, input().split()))
c = collections.Counter(arr)

counts = list(c.values())[::-1]

if len(counts)==1:
  print(0)
else:
  value = 0
  for num in arr:
    value += len([1 for x in arr if x<num])
  out_arr = value*K*(K-1)//2
  
  in_arr = 0
  for j,num in enumerate(arr):
    in_arr += len([1 for x in arr[j+1:] if x<num])
  in_arr = in_arr*K
  print((out_arr+in_arr)%1000000007)

Solution (Python):
N,K = map(int, input().split())
A = list(map(int, input().split()))
Ans = 0
 
count1 = (K * (K+1) // 2) % 1000000007
count2 = ((K-1) * K // 2) % 1000000007



 
for i in range(N):
 
  for j in range(N):
 
    if A[i] > A[j]:
      if i < j:
        Ans = Ans + count1
      else:
        Ans = Ans + count2
      
      if Ans > 1000000007:
        Ans = Ans % 1000000007  
 
 
print(int(Ans))

Solution (Python):
n,k = list(map(int,input().split()))
num_list = list(map(int,input().split()))
next_list = []
mod = ((10**9)+7)
up = 0
exup = 0
ans = 0
for i in range(n):
    for j in num_list:
        if num_list[0] > j:
            up+=1
    next_list.append(num_list.pop(0))
for i in range(n):
    for j in next_list:
        if next_list[-1] > j:
            exup+=1
    del next_list[-1]
ans = up*k*(k+1)//2 + exup*(k-1)*k//2

print(int(ans%mod))

Solution (Python):

N, K = map(int, input().split())
A = list(map(int, input().split()))
INF = 10 ** 9 + 7

inner = 0
outer = 0
cnt = 0
ans = 0

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

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

ans = (inner * K + ((K * (K - 1)) // 2) * outer) % INF
print(ans)

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

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

C = [0] * (max(A)+1)
a1 = 0
a2 = 0

for i in range(n):
    C[A[i]] += 1
    a2 += sum(C[A[i]+1:])
for i in range(n):
    a1 += sum(C[A[i]+1:])

a1 %= mod
a2 %= mod

k %= mod

if k % 2 == 0:
    kk = [k//2, k-1]
else:
    kk = [k, (k-1)//2]

ans = 0
ans += a2*k % mod
ans2 = a1*kk[0] % mod
ans2 *= kk[1] % mod
ans += ans2 % mod

print(int(ans % mod))

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

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

tmp1 = 0
tmp2 = 0

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

for i in range(N):
    for j in range(N):
        if aLst[i] > aLst[j]:
            tmp2 += 1

ans = (tmp1 * (K)) + ((K * ((K - 1)) // 2) * tmp2)
print(ans % INF)

Solution (Python):
N, K = map(int,input().split())
An = list(map(int,input().split()))
f_count = 0
r_count = 0

for i in range(N):
    for j in range(N):
        if i < j:
            if An[i] < An[j]:
                f_count += 1
            elif An[i] > An[j]:
                r_count += 1

Ans = (f_count * K*(K-1)//2 + r_count * (K*(K+1)//2)) % (10**9+7)

print(int(Ans))

Solution (Python):
import numpy as np

MOD = 10**9 + 7
N, K = map(int, input().split())
Alist = list(map(int, input().split()))

l = 0
r = 0
for i in range(N):
    for j in range(N):
        if Alist[i] > Alist[j]:
            if i < j:
                r += 1
            if i > j:
                l += 1

Kl = int((K * (K - 1) // 2) % MOD)
Kr = int((K * (K + 1) // 2) % MOD)
ans = (l * Kl + r * Kr) % MOD

print(ans)

Solution (Python):

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

naibu = 0
for i in range(n):
    for j in range(i+1, n):
        if A[i] > A[j]:
            naibu += 1
gaibu = 0
A2 = A
for i in range(n):
    for j in range(n):
        if A[i] > A2[j]:
            gaibu += 1

total = naibu*k + gaibu*(k*(k-1)//2)
print(total%mod)

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


diff = []
npA = np.array(A)
lenA = len(A)
for a in A:
    temp = list(np.array([a for i in range(lenA)]) - npA)
    diff.append(temp)

D = np.array(diff)

upD = np.triu(D,k=1)

upC = np.count_nonzero(upD>0)
dwC = np.count_nonzero(upD<0)

ans = (K*(K+1)//2)*upC + ((K-1)*K//2)*dwC
print(ans%(1000000007))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

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

MOD = pow(10,9) + 7

p = 0

c = 0
d = 0
for i in range(n):
  for j in range(i+1,n):
    if(a[i] > a[j]):
      c += 1
      d += 1
    elif(a[i] < a[j]):
      d += 1


ans = int(c * k % MOD) + int( (k *(k-1)//2) % MOD * d)
ans = int(ans%MOD)

print(ans)

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

H = [[b < a for b in A[:i]].count(True) for i, a in enumerate(A)]  
T = [[b < a for b in A[i+1:]].count(True) for i, a in enumerate(A)]  

print(sum(h*K*(K-1)//2 + t*K*(K+1)//2 for h, t in zip(H, T)) % MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

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

MOD = pow(10,9) + 7

p = 0

c = 0
d = 0
for i in range(n):
  for j in range(i+1,n):
    if(a[i] > a[j]):
      c += 1
      d += 1
    elif(a[i] < a[j]):
      d += 1


ans = int(c * k % MOD) + int( (k *(k-1)//2) % MOD * d)
ans = int(ans%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

cnt=(x*k)+(k*(k-1)//2*y)
print(cnt%mod)

Solution (Python):
import math

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

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

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

cnt = cnt_1 * K + cnt_2 * ((K-1)*K//2)

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

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

cna=0
for i,a in enumerate(A):
    for at in A[i+1:]:    
        if a>at:
            cna+=1

cna2=0
for a in A:
    for at in A:    
        if a>at:
            cna2+=1


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







print((K*cna+kt*cna2)%tmp)

Solution (Python):
import math

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

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

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

cnt = cnt_1 * K + cnt_2 * int((K-1)*K//2)

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

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

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

cna=0
for i,a in enumerate(A):
    for at in A[i+1:]:    
        if a>at:
            cna+=1

cna2=0
for a in A:
    for at in A:    
        if a>at:
            cna2+=1


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

print((K*cna+kt*cna2)%tmp)

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


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

ans = 0
ans = (ans + (K * cnt_self)) % (10 ** 9 + 7)

coeff = (K * (K - 1) // 2) % (10 ** 9 + 7)
ans = (ans + (coeff * cnt_left)) % (10 ** 9 + 7)

print(ans)

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):
n, k = map(int, input().split())
lis = list(map(int, input().split()))
c1, c2 = 0, 0
for i in range(n):
        for j in range(n):
                if lis[i] > lis[j]:
                        c2 += 1
                        if j > i:
                                c1 += 1
ans = c1*k + c2*k*(k-1)//2
print(ans % 1000000007)

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re




import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]



def c(seq):
    ans = 0
    for i in range(0, len(seq)):
        for j in range(i, len(seq)):
            if seq[i] > seq[j]:
                ans += 1
    return ans

def main():
    N, K = l_inpl()
    A = l_inpl()
    a = c(A)
    b = c(A*2)
    print((a*K+(b-2*a)*K*(K-1)//2)%MOD)

if __name__ == "__main__":
    main()

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

Solution (Python):
from itertools import groupby

R = lambda: map(int, input().split())
n, k = R()
a = list(R())
w = [0] * n

def merge(b, e):
    m = b + (e - b) // 2
    i, j = b, m
    r = k = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[k] = a[i]
            i += 1
        else:
            r += m - i
            w[k] = a[j]
            j += 1
        k += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + k] = w[:k]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    m = b + (e - b) // 2
    return mergesort(b, m) + mergesort(m, e) + merge(b, e)


r = k * mergesort(0, n)
c = n * (n - 1) // 2
for v, g in groupby(a):
    x = sum(g) // v
    c -= x * (x - 1) // 2
print((r + c * k * (k - 1) // 2) % (10**9 + 7))

Solution (Python):
from itertools import groupby

R = lambda: map(int, input().split())
n, k = R()
a = list(R())
w = [0] * n

def merge(b, e):
    m = b + (e - b) // 2
    i, j = b, m
    r = k = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[k] = a[i]
            i += 1
        else:
            r += m - i
            w[k] = a[j]
            j += 1
        k += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + k] = w[:k]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    m = b + (e - b) // 2
    return mergesort(b, m) + mergesort(m, e) + merge(b, e)


r = k * mergesort(0, n)
c = n * (n - 1) // 2
for v, g in groupby(a):
    x = sum(map(bool, g))
    c -= x * (x - 1) // 2
print((r + c * k * (k - 1) // 2) % (10**9 + 7))

Solution (Python):
from bisect import bisect

def solve():
	mod = 10**9+7
	n,k,*a = map(int,open(0).read().split())
	b = []
	ans = 0
	for j,x in enumerate(a):
		i = bisect(b,x)
		ans += (j-i)*k
		ans %= mod
		b.insert(i,x)
	bef = max(a)
	j=0
	for i,cur in enumerate(b[::-1]):
		if cur!=bef:
			j = i
			bef = cur
		ans += k*(k-1)*j//2
		ans %= mod
	print(ans%mod)

if __name__=="__main__":
	solve()

Solution (Python):
from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
ans = 0
inf = 10 ** 9 + 7

for i in range(N):
    cnt_left = 0
    cnt_right = 0
    for j in range(N):
        if A[j] < A[i]:
            if j < i:
                cnt_left += 1
            else:
                cnt_right += 1
    ans += (cnt_right * (K + 1) * K // 2) % inf
    ans += (cnt_left * (K - 1) * K // 2) % inf

print(ans % inf)

Solution (Python):
from itertools import groupby

R = lambda: map(int, input().split())
n, k = R()
a = list(R())
w = [0] * n

def merge(b, e):
    m = b + (e - b) // 2
    i, j = b, m
    r = k = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[k] = a[i]
            i += 1
        else:
            r += m - i
            w[k] = a[j]
            j += 1
        k += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + k] = w[:k]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    m = b + (e - b) // 2
    return mergesort(b, m) + mergesort(m, e) + merge(b, e)


r = k * mergesort(0, n)
c = n * (n - 1) // 2
for v, g in groupby(a):
    x = sum(g) // v
    c -= x * (x - 1) // 2
print((r + c * k * (k - 1) // 2) % (10**9 + 7))

Solution (Python):
from itertools import groupby

R = lambda: map(int, input().split())
n, k = R()
a = list(R())
w = [0] * n

def merge(b, e):
    m = b + (e - b) // 2
    i, j = b, m
    r = k = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[k] = a[i]
            i += 1
        else:
            r += m - i
            w[k] = a[j]
            j += 1
        k += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + k] = w[:k]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    m = b + (e - b) // 2
    return mergesort(b, m) + mergesort(m, e) + merge(b, e)


r = k * mergesort(0, n)
c = n * (n - 1) // 2
for _, g in groupby(a):
    x = sum(1 for _ in g)
    c -= x * (x - 1) // 2
print((r + c * k * (k - 1) // 2) % (10**9 + 7))

Solution (Python):
from collections import Counter

R = lambda: map(int, input().split())
n, k = R()
a = list(R())
w = [0] * n

def merge(b, e):
    m = b + (e - b) // 2
    i, j = b, m
    r = k = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[k] = a[i]
            i += 1
        else:
            r += m - i
            w[k] = a[j]
            j += 1
        k += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + k] = w[:k]
    return r        
    
def mergesort(b, e):
    if e - b < 2:
        return 0
    m = b + (e - b) // 2
    return mergesort(b, m) + mergesort(m, e) + merge(b, e)


r = k * mergesort(0, n)
c = n*(n-1)//2 - sum(x*(x-1)//2 for x in Counter(a).values())
print((r + c * k * (k - 1) // 2) % (10**9 + 7))

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

def resolve():
    n, k = map(int, input().split())
    aa = list(map(int, input().split()))

    a1 = 0
    for i in range(n-1,-1,-1):
        for j in range(i,-1,-1):
            if aa[i] < aa[j]:
                a1 += 1

    if k == 1:
        print(a1)
        return

    a2 = 0
    aa2 = aa * 2

    for i in range(2*n-1,-1,-1):
        for j in range(i,-1,-1):
            if aa2[i] < aa2[j]:
                a2 += 1

    if k == 2:
        print(a2)
        return

    a3 = 0
    aa3 = aa * 3

    for i in range(3*n-1,-1,-1):
        for j in range(i,-1,-1):
            if aa3[i] < aa3[j]:
                a3 += 1

    b1 = a2 - a1
    b2 = a3 - a2
    d = b2 - b1

    s = int(a1 + ((k-1) * (2 * b1 + (k-2) * d))//2)
    ans = s % (10**9 + 7)
    print(ans)



resolve()

Solution (Python):
s=list(map(int,input().split()))
t=list(map(int,input().split()))
if s[0]==1:
  print(0)
else:
  b=0
  for i in range(s[0]):
    a=0
    for j in range(s[0]):
      if t[i]>t[j]:
        a=a+1
    b=b+a*s[1]*(s[1]-1)//2
    b=b%1000000007
  b=b%1000000007
  for v in range(s[0]-1):
    a=0
    for w in range(v+1,s[0]):
      if t[v]>t[w]:
        a=a+1
    b=b+a*s[1]
    b=b%1000000007
  b=b%1000000007
  print(int(b))

Solution (Python):
n, k = input().split()
N = int(n)
K = int(k)
A = [int(a) for a in input().split()]
countAList = []
countBList = []
for j in range(N):
    countA = 0
    countB = 0
    for i in range(N):
        if A[i] < A[j]:
            countB += 1
            if i > j:
                countA += 1
    countAList.append(countA)
    countBList.append(countB)
result = 0

for a, b in zip(countAList, countBList):
    result += int(K * a) + int(b * K * (K - 1) // 2)
    result %= 10 ** 9 + 7
print(result)

Solution (Python):
from itertools import groupby

R = lambda: map(int, input().split())
n, k = R()
a = list(R())
w = [0] * n

def merge(b, e):
    m = b + (e - b) // 2
    i, j = b, m
    r = k = 0
    while i < m and j < e:
        if a[i] <= a[j]:
            w[k] = a[i]
            i += 1
        else:
            r += m - i
            w[k] = a[j]
            j += 1
        k += 1
    a[e - m + i: e] = a[i: m]
    a[b: b + k] = w[:k]
    return r        
  
  
def mergesort(b, e):
    if e - b < 2:
        return 0
    m = b + (e - b) // 2
    return mergesort(b, m) + mergesort(m, e) + merge(b, e)


r = k * mergesort(0, n)
c = n * (n - 1) // 2
for _, g in groupby(a):
    x = sum(1 for _ in g)
    c -= x * (x - 1) // 2
print((r + c * k * (k - 1) // 2) % (10**9 + 7))

Solution (Python):
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a_tentou = [0 for i in range(n)]
a_tentou2 = [0 for i in range(n)]
mod = 10 **9 + 7

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

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

answer = 0
for i in range(n):
    answer += a_tentou[i] * k
    answer += a_tentou2[i] * (k - 1) * k // 2
    answer = answer % mod
print(answer)

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

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

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

total_inv = k * intra_inv + k * (k - 1) // 2 * inter_inv
dst = int(total_inv % (10**9 + 7))
print(dst)

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

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

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

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

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

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

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

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

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

ans = 0
mod = 10 ** 9 + 7

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

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

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

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

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

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

ans = (p * K) % 1000000007 + (q * K * (K-1) // 2) % 1000000007

print(ans % 1000000007)

Solution (Python):
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
numc = 0
numf = 0

for i in range(0, N):
    for j in range(0,i):
        if A[j] > A[i]:
            numc += 1
        if A[i] > A[j]:
            numf += 1
numbers = (numc*K*(K+1) + numf*K*(K-1))//2
 
ans = int(numbers % (10**9 + 7))
print(ans)

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

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

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

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

ans = (p * K) % 1000000007 + (q * K * (K-1) // 2) % 1000000007

print(ans % 1000000007)

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

cnt1 = 0
for i in range(len(a)-1):
    for j in range(i, len(a)):
        if a[i] > a[j]:
            cnt1 += 1

a2 = a * 2
cnt2 = 0
for i in range(len(a)):
    for j in range(len(a), len(a2)):
        if a2[i] > a2[j]:
            cnt2 += 1

print((cnt1 * k + cnt2 * k * (k-1) // 2) % MOD)

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

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

mod = 1000000007


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

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

ans = (syokiti_A * K) % mod + (syokiti_B * K * (K-1) // 2) % mod
print(int(ans) % mod)

Solution (Python):


def main():
    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,i):
            if A[i] > A[j]:
                outer += 1
        for j in range(i+1,N):
            if A[i] > A[j]:
                inner += 1
                outer += 1
    count = inner * K + outer * K * (K-1) // 2
    count = count % (10**9 +7)
    print(count)



if __name__ == "__main__":
    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 = f-g
k = k











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

exit()

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)



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

exit()

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

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

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

Solution (Python):
N, K = map(int, input().split())
A = [int(_) for _ in input().split()]
B = 10 ** 9 + 7
work = 0
ans1, ans2 = 0, 0
for i, p in enumerate(A):
    
    for j in range(i + 1, N):
        if p > A[j]:
            ans1 += 1
    
    for q in A:
        if p > q:
            ans2 += 1

ans1 *= K
ans2 *= (K * (K - 1)) // 2
ans = ans1 + ans2
print(int(ans % B))