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 copy

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

const = 1000000007
c = 0
d = 0

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

b = copy.deepcopy(a)

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





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

print(int(ans) % const)

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 count_inversion(sequence):
    count = 0
    for i in range(1,len(sequence),1):
        for j in range(i,len(sequence),1):
            if sequence[i-1] > sequence[j]:
                count += 1
    return count

def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

def main():
    N, K = l_inpl()
    A = l_inpl()
    a1 = count_inversion(A)
    b1 = (count_inversion(A*2) - count_inversion(A))
    b2 =  (count_inversion(A*3) - count_inversion(A*2))
    c1 = b2 - b1
    print((a1*K+c1*(K%MOD)*((K-1)%MOD)//2)%MOD)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import bisect
input = sys.stdin.readline
 
def main():
    n,k = map(int,input().split())
    a=list(map(int,input().split()))
    cnta=0
    cntb=0
    for i in range(n-1):
        for j in range(n-1-i):
            j+=i+1
            if(a[i]>a[j]):
                cnta+=1
    for i in range(n):
        for j in range(n):
            if(a[i]>a[j] and i!=j):
                cntb+=1
    cntak=int(  (cnta*k) % (1000000007)  )
    x=int(  ((k*(k-1))//2) % (1000000007)  )
    cntbk=int(  (cntb*x) % (1000000007)  )
    
    ans=int(  (cntak+cntbk) % (1000000007)  )
    
    print(ans)
    
main()

Solution (Python):
import sys

input = sys.stdin.readline


def bubble_sort(a):
    b = a[:]
    cnt = 0
    n = len(b)
    for i in range(n):
        for j in range(n - 1, i, -1):
            if b[j] < b[j - 1]:
                b[j], b[j - 1] = b[j - 1], b[j]
                cnt += 1
                cnt %= mod
    return cnt, b


mod = 10 ** 9 + 7

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

cnt, b = bubble_sort(a)
ans = cnt * k
ans %= mod


b.sort(reverse=True)

dd = dict()

sm = 0
for i, bb in enumerate(b):
    if dd.get(bb, None) is None:
        dd[bb] = i
        sm += i
    else:
        sm += dd[bb]

ans += (k - 1) * k // 2 * sm
ans %= mod

print(ans)

Solution (Python):
from decimal import *

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

a = Decimal(str(K - 1))
b = Decimal(str(K))
c = Decimal(str(K + 1))

d = Decimal(a*b/2)
e = Decimal(b*c/2)







d = d % 1000000007
e = e % 1000000007






count1 = int(e)
count2 = int(d)




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 = map(int, input().split())
A = list(map(int, input().split()))
mod = 1000000007

ans = 0
for i in range(len(A)):
    cnt1 = 0
    cnt2 = 0
    for j in range(i, i+len(A)):
        if A[i] > A[j%(len(A))]:
            if j < len(A):
                cnt1 += 1
            else:
                cnt2 += 1
    ans += (cnt1 * K * (K+1) // 2)
    ans += (cnt2 * (K-1) * K // 2)
    ans %= mod
print(ans)

Solution (Python):
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin

mod = 1000000007


def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]


def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def main():
    N, K = map(int, input().split())
    A = [int(x) for x in input().split()]

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


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

    
    ans = ((2*ini+(K-1)*diff) % (10**9+7)) * K % (10**9+7)
    ans = ans * mod_inv(2,mod) % (10**9+7)
    print(ans)

input = lambda: stdin.readline().rstrip()
main()

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

for i in range(len(a)):
    p=sum([1 for j in a[i:] if a[i]>j])
    q=sum([1 for j in a if a[i]>j])
   
    s=int(p*k%(1000000000+7))
    t=int(q*(((k-1)*k)//2)%(1000000000+7))
    ans+=s+t


print(int(ans%(1000000000+7)))

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









count_with_seq = 0
deal = 0
for i in range(N) :
    ai = A_list[i]
    for k in range(i+1,N) :
        deal += 1
        ak = A_list[k]
        if (ai > ak) :
            
            count_with_seq += 1

count_without_seq = 0
for ai in A_list :
    for ak in A_list :
        if (ai > ak) :
            count_without_seq += 1







total_count = count_with_seq * K

rep = (1 + (K-1)) * (K-1) // 2
total_count += count_without_seq * rep

print(total_count % 1000000007)

Solution (Python):



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











C = [[A[i], i] for i in range(N)]

C = sorted(C, key=lambda x: x[0], reverse=False)


tento_dict = {C[0][1]: 0}  
for i in range(1, N):
    if C[i][0] == C[i-1][0]:
        tento_dict[C[i][1]] = tento_dict[C[i-1][1]]
    else:
        tento_dict[C[i][1]] = i





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

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

Solution (Python):

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]


def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

nk = input().split(" ");
n = int(nk[0]);
k = int(nk[1]);
a = input().split(" ");

waru = 10 ** 9 + 7;

for i in range(n) :
	a[i] = int(a[i]);

kaisu = [0] * n;
usiro = [0] * n;

for i in range(n) :
	for j in range(n) :
		if a[i] > a[j] :
			kaisu[i] += 1;
			if i < j :
				usiro[i] += 1;

ans = 0;
for i in range(n) :
	ans += ((((((k-1)%waru) * (k%waru) )%waru) *mod_inv(2,waru)) * (kaisu[i]%waru) + ((k%waru)*(usiro[i]%waru))%waru)%waru;
		
	
print(int(ans%waru));

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

listl = [0]*n
listr = [0]*n

tmpmax = 0
for i in range(1,n):
    tar = lista[i]
    for j in range(i,-1,-1):
        if lista[j]<tar:
            
            
            listl[i] +=1

for i in range(n-2,-1,-1):
    tar = lista[i]
    for j in range(i,n):
        if lista[j]<tar:
            
            
            listr[i] += 1
            
            
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

ans = 0
i2 = mod_inv(2,((10**9)+7))
for i in range(n):
    f = (listl[i]*(k-1)+listr[i]*k)%((10**9)+7)
    t = (listr[i])%((10**9)+7)
    
    ans += int(((f+t)*k)*i2)
    
    ans = int(ans%((10**9)+7))
    
print(ans)

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


val = 0
for i in range(n):
    inv = 0
    sub = 0
    B = A[i + 1:] + A[:i]
    for j in range(n - 1):
        if A[i] > B[j] and j >= n - i - 1:
            inv += 1
            sub += 1
        elif A[i] > B[j]:
            inv += 1

    val += inv * k * (k + 1) // 2 - sub * k
    val %= 10 ** 9 + 7
    
print(val)

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

mlist=[0]*n
nlist=[0]*n

for i in range(n):
    for j in range(n):
        if alist[i]>alist[j] and i>j:
            mlist[i]+=1
        elif alist[i]>alist[j] and i<j:
            nlist[i]+=1


kotae=0
for i in range(n):
    if k%2==1:
        a1=k*int((k+1)/2)
        a2=k*int((k-1)/2)
    else:
        a1=int(k/2)*(k+1)
        a2=int(k/2)*(k-1)
    kotae+=nlist[i]*a1
    kotae+=mlist[i]*a2
    kotae=kotae%(10**9+7)

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

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

Solution (Python):
mod=1000000007

pi=3.1415926535897932
IS=float('inf')

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=a*2
ans=chk=0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i]>a[j]:
            chk+=1
            chk%=mod

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

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

total = (K + 1) * K // 2
count = 0
for i, Ai in enumerate(A):
    for j in range(i, len(A)):
        if Ai > A[j]:
            count += 1 
sortA = sorted(A, reverse=True)
sort_count = 0
for i, sortAi in enumerate(sortA):
    for j in range(i, len(sortA)):
        if sortAi > sortA[j]:
            sort_count += 1 
            
sub = (sort_count - count) * K
print((total * sort_count - sub) % (10**9 + 7))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
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 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

class BIT:
    def __init__(self, n):
        
        self.size = n
        self.tree = [0] * (n+1)
 
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s
    
    
    def get(self, l, r=None):
        
        if r is None: r = l+1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

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


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

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

bit = BIT(M+1)
org = 0
for i in range(N-1, -1, -1):
    bit.add(A[i], 1)
    
    org += bit.sum(A[i]-1)
bit = BIT(M+1)
org2 = 0
for i in range(N):
    bit.add(A[i], 1)
    
    org2 += bit.sum(A[i]-1)

ans = (org*K+(org+org2)*get_sum(K-1)) % MOD
print(ans)

Solution (Python):
n,k=map(int, input().split())
a=list(map(int, input().split()))
cnt=0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        if a[i]>a[j]:
            cnt+=1
ans=cnt*k
cnt2=0
aa=sorted(a,reverse=True)
for i in range(len(aa)):
    for j in range(i+1,len(aa)):
        if aa[i]>aa[j]:
            cnt2+=1
ans2=cnt2*((k*(k-1))//2)
print((ans+ans2)%((10**9)+7))

Solution (Python):
mod=1000000007
n,k=map(int,input().split())
A=list(map(int,input().split()))
cnt1,cnt2=0,0
for i in range(n):
    for j in range(n):
        if A[i]>A[j]:
            if i<j:
                cnt1+=1
            if i>j:
                cnt2+=1
cnt1*=k*(k+1)//2
cnt2*=k*(k-1)//2
print((cnt1+cnt2)%mod)

Solution (Python):
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
ans_base = 0
ans_base_rev = 0
big = (10**9)+7
for i in range(N-1):
    for k in range(i + 1, N):
        if A[i] > A[k]:
            ans_base += 1
        elif A[i] < A[k]:
            ans_base_rev += 1



val_p = (K * (K + 1)) // 2
val_m = (K * (K - 1)) // 2


ans = ans_base * val_p + ans_base_rev * val_m
ans = ans % big
print(int(ans))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = (10**9) + 7
after = sum([len(list(filter(lambda x: A[i] > x, A[i+1:]))) for i in range(N - 1)])%m
_all = sum([len(list(filter(lambda x: A[i] > x, A))) for i in range(N)])%m

k = (K*K-(K*(K+1)//2))%m

print((
  (after*K)%m
  +(_all*k)%m
)%m)

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

mod=10**9+7


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


rightnum=0            
for i in range(n):
    a=a_list[i]
    for a_all in a_list:
        if a>a_all:
            rightnum+=1

samecol=(k*(k-1)//2)%mod
ans=(samecol*rightnum)%mod
ans=(ans+first*k)%mod
print(ans)

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

l=[]
l1=[]
for i in range(n):
    p=0
    for j in a:
        if j>a[i]:
            p+=1
    l.append(p)

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

ans=0
mod=10**9+7
for i in range(n):
    ans+=k*(2*l1[i]+(k-1)*(l[i]))//2
    ans=ans%mod
print(ans)

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

ans = 0

for i in range(n-1):
    b = a[i]
    count = 0
    for j in range(i+1, n):
        if b > a[j]:
            count += 1
    if count == 0:
        continue
    ap = (k * (k+1) // 2)
    tmp = (count * ap)
    ans += tmp
    ans %= MOD


for i in range(n):
    b = a[i]
    count = 0
    for j in range(i):
        if b > a[j]:
            count += 1
    if count == 0:
        continue
    ap = ((k-1) * k // 2)
    tmp = (count * ap)
    ans += tmp
    ans %= MOD
print(int(ans))

Solution (Python):
import math
n,k=map(int, input().split())
a=list(map(int, input().split())) 
count=0
ans=0
x=0
y=0
y=(k+1)*k//2
y=y%(10**9+7)
b=sorted(a)
for i in range(n):
    for j in range(i,n):
        if a[i]>a[j]:
            count+=1
    for p in range(n):
        if b[p]==a[i]:
            x=p
            break
    
    ans+=count*k+x*(k-1)*k//2
    count=0
            

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

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

Solution (Python):
import sys



mod = 7 + (10**9)
		
def main():
	n, k = map(int, input().split())
	aa_list=list(map(int, input().split()))
	
	ret = 0
	for i, v in enumerate(aa_list):
		a=len([x for x in aa_list[:i] if x < v])
		b=len([x for x in aa_list[i+1:] if x <v])
		ret += a*k*(k-1)//2
		ret += b*k*(k+1)//2
	print(ret%mod)
	
	



if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 + 7
length = len(A)
R_down = [0]*length
L_down = [0]*length

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

    R_down[i] = count

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

    L_down[i] = count

R = sum(R_down)*k*(k+1)//2
L = sum(L_down)*(k-1)*k//2
ans = (R + L) % mod
print(int(ans))

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

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

import bisect

A.sort()
v2 = 0
for a in A:
    v2 += bisect.bisect_left(A, a)

mod = 10 ** 9 + 7
ans = (v1 * K) % mod

if K > 1:
    tmp = (K - 1) % mod
    tmp = (tmp * K // 2) % mod
    
    ans += tmp * v2
ans = ans % mod




print(ans)

Solution (Python):

n,k=map(int,input().split())
lis=list(map(int,input().split()))
count=0
for i in range(len(lis)):
  for j in range(i+1,len(lis)):
    if lis[i]>lis[j]:
      count+=1     
lista=[]
for i in lis:
  counta=0
  for j in lis:
    
    if i>j:
      counta+=1
  lista.append(counta)
print((count*k+sum(lista)*(k*(k-1)//2))%(10**9+7))

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

low=0
high=0
eq=0
for i in range(N):
  for j in range(i+1,N):
    if(ls[i]>ls[j]):
      low+=1
    elif(ls[i]<ls[j]):
      high+=1
    else:
      eq+=1

ans=0
ans+=low*K*(K+1)//2
ans+=high*K*(K-1)//2
ans=ans%(1000000007)
print(ans)

Solution (Python):

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

def count_inversion(target_list):
    return sum(sum(m<n for m in target_list[i+1:]) for i,n in enumerate(target_list))

A_list_copy = A_list
invension_increase = 0
for i in set(A_list):
    max_num = max(A_list_copy)
    max_count = A_list_copy.count(max(A_list_copy))
    A_list_copy = [num for num in A_list_copy if num != max_num]
    invension_increase += max_count * len(A_list_copy)

ans_count = count_inversion(A_list) * K
ans_count += invension_increase * K * (K - 1) // 2

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

Solution (Python):
tmp = [int(i) for i in input().split(" ")]
n = tmp[0]
k = tmp[1]
a = [int(i) for i in input().split(" ")]
import numpy as np
a = np.array(a)
uni = np.unique(a)
co = [np.sum(a==i) for i in uni]
ind = np.array([np.sum(co[:uni.tolist().index(i)]) for i in a]).astype(np.int32)
c = 0

for i in range(len(a)):
    c += np.sum(a[i:]<a[i])
m = 10**9+7
tm = int(c)*int(k) % m
if k % 2 == 0:
    t = k * (k//2-1) + k//2
    t %= m
else:
    t = k * (k//2)
    t %= m
print((int(np.sum(ind))*t+tm) % m)

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

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

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

Solution (Python):
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
a = N*[0]
b = N*[0]

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

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

Solution (Python):
from sys import stdin
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()]
def count_inversion(sequence):
    r = [0]*len(sequence)
    l = [0]*len(sequence)
    for i in range(1,len(sequence),1):
        cnt_r = 0
        cnt_l = 0
        for j in range(i,len(sequence),1):
            if sequence[i-1] > sequence[j]:
                cnt_r += 1
            elif sequence[i-1] < sequence[j]:
                cnt_l += 1
        r[i-1] = cnt_r
        l[i-1] = cnt_l
    return sum(r),sum(l)
r,l = count_inversion(A)
ans = ((K*(K+1))//2)*r
ans += (((K*(K-1))//2))*l
ans = ans%mod
print(ans)

Solution (Python):
import sys

def process(data):
	count1 = 0
	count2 = 0

	N = int(data[0][0])
	K = int(data[0][1])
	A = list(map(int, data[1]))

	for i in range(len(A)-1):
		for j in range(i+1, len(A)):
			if A[i] > A[j]:
				count1 += 1
	A.reverse()
	
	for i in range(len(A)-1):
		for j in range(i+1, len(A)):
			if A[i] > A[j]:
				count2 += 1	

	count1 = count1 * K*(K+1)/2
	count2 = count2 * (K-1)*K/2

	count = count1 + count2

	count = count % (10**9+7)
	return count



def main():
	d = []
	for i in range(2):
		data = raw_input()
		data = data.split(" ")
		d.append(data)
	print(process(d))

if __name__ == '__main__':
    main()

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

result = 0

if K == 1:
    B = A
    for i in range(N):
        for j in range(i+1, N):
            if B[i] > B[j]:
                result += 1
else:
    B = A + A
    for i in range(N):
        C = 0
        D = 0
        E = 0
        for j in range(i+1, N):
            if B[i] > B[j]:
                C += 1
        for j in range(N, N+i+1):
            if B[i] > B[j]:
                D += 1
        E = K * (K * (C + D) + C - D) // 2
        E = E % (10**9 + 7)
        result += E
    result = result % (10**9 + 7)

print(result)

Solution (Python):
import collections

from scipy.misc import comb


NUM_MOD = 10 ** 9 + 7


len_arr, num_repeat = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))

differ = [len(list(filter(arr[i].__gt__, arr[i+1:]))) for i in range(0, len_arr)]
ans_internal = sum(differ)
num_kind = len(collections.Counter(arr))

if num_kind == 1:
    ans_external = 0
else:
    differ = [len(list(filter(arr[i].__gt__, arr))) for i in range(0, len_arr)]
    ans_external = sum(differ)

num_comb = comb(num_repeat, 2, exact=True)
ans = num_comb * ans_external + num_repeat * ans_internal


print(ans % NUM_MOD)
exit(0)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
def modpow(a,n,mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

def modinv(a,mod):
    return modpow(a,mod - 2,mod)


one = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] > A[j]:
            one+=1
two = 0
AA = A+A
for i in range(N*2):
    for j in range(i+1,N*2):
        if AA[i] > AA[j]:
            two+=1
two -= one*2
MOD = 10**9+7

print((one*K%MOD + two*(((K-1)*(K)//2)))%MOD)

Solution (Python):

MOD = 10**9 + 7


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

    init = [0] * N
    diff = [0] * N
    for i, a in enumerate(A):
        init[i] = len(list(filter(lambda x: x < a, A[i:])))
        diff[i] = len(list(filter(lambda x: x < a, A)))

    ans = sum((K * (2 * ini + (K - 1) * dif) // 2) %
              MOD for ini, dif in zip(init, diff)) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  l1=LI()
  l2=sorted(l1)

  ans=0
  _ans=0
  for i,x in enumerate(l1):
    _l=sorted(l1[i:])
    ans+=bisect.bisect_left(_l,x)
    _ans+=bisect.bisect_left(l2,x)
  

  return (ans*k+(_ans*(k-1)*k//2))%mod



print(main())

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

cnt = 0
for i in range(N):
    k = 0
    for j in range(i):
        if A[i]>A[j]:
            k += 1
    cnt += (K-1)*(k + k*(K-1))//2

    l = 0
    for j in range(i+1, N):
        if A[i]>A[j]:
            l += 1
    cnt += K*(l + l*K)//2

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

Solution (Python):

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

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

mod = 1000000007

need = (k * (k + 1)) // 2
need2 = ((k - 1) * k) // 2
ans = 0

freq = []
before = []
for i in range(0, 3000):
	freq.append(0)
	before.append(0)
	

for i in range(0, n):
	for j in range(i + 1, n):
		if(a[i] > a[j]):
			freq[i] += 1
			
	j = i - 1
	while j >= 0:
		if(a[i] > a[j]):
			before[i] += 1
		j -= 1
		
	ans += (freq[i] * need)
	ans += (before[i] * need2)


print(ans % mod)

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

M = 1000000007

answer = 0
for i in range(n):
    p = 0
    q = 0
    for j in range(n):
        if a[j] < a[i]:
            p += 1
            if j > i:
                q += 1
    answer += q * k + p * k * (k - 1) // 2
    answer %= M

print(answer)

Solution (Python):
import bisect
mod = 10**9+7
def main():
    n,k=map(int,input().split(' '))
    a = list(map(int,input().split(' ')))
    a_fall= 0
    a_rev = sorted(a,reverse=True)
    u_cnt = 0
    for i in range(n-1):
        a_sorted = sorted(a[i+1:])
        a_fall += bisect.bisect_left(a_sorted,a[i])
        a_fall %=mod
    a_sorted = sorted(a)
    for i in a:
        u_cnt += bisect.bisect_left(a_sorted,i)
    ans = a_fall*k+u_cnt*(k-1)*k//2
    ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

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

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

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

m = (K-1)*K//2
val = count_ * m + count_self * K
            
print(divmod(val, 10**9+7)[1])

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

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

ans = 0

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

ansk = 0

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

print((ans * k + ansk * ((k-1)*k //2)) % (10**9 + 7))

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

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

a_sorted = sorted(a)

bit = [0] * 2001

inversion = 0
for i in range(n):
  bit[a[i]] += 1
  s = 0
  for j in range(a[i]+1):
    s += bit[j]
  inversion += i + 1 - s
  
inversion *= k
  
for i in range(n):
  inversion += (a_sorted.index(a[i]) * k * (k - 1)) // 2
  
print(inversion % int(10**9 + 7))

Solution (Python):
import bisect

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

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

res = 0
b = sorted(a)
for e in b:
    kw = bisect.bisect_right(b,e)
    res += n-kw

print((k*ass%mod+( (k*(k-1)//2)%mod )*res%mod)%mod)

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

a1=[int(i) for i in input().split()]
b1=[]
for i in range(len(a1)):
    b1.append([sum(x>a1[i] for x in a1[:i]),0])

l=len(a1)
a1.extend(a1)

for i in range(l):
    
    b1[i][1]=sum(x>a1[i+l] for x in a1[:i+l])

c=0
for i in range(len(b1)):
    c+=(2*b1[i][0]+(k-1)*(b1[i][1]-b1[i][0]))*k//2
    if c>10**9+7:
        c=c%(10**9+7)

print(c)

Solution (Python):
mod = 10**9+7
n , k = map(int,input().split())
arr =[ int(i) for i in input().split() ]
cnt_tot = [ 0 for i in range(2005) ]
bit = [ 0 for i in range(2005) ]
def sum(r):
    global bit
    ret = 0
    while r >= 0:
        ret += bit[r]
        r = ( r & (r+1) ) - 1
    return ret

def add(idx, delta):
    global bit
    while idx < 2005:
        bit[idx] += delta
        idx = idx | (idx+1)

def sum2(l,r):
    return sum(r) - sum(l-1)

for i in range(n):
    cnt_tot[arr[i]] += 1
for i in range(1,2005):
    cnt_tot[i] += cnt_tot[i-1]

ans = 0
full = (k-1) * (k) * pow(2,mod-2,mod)
for i in range(n):
    ans += (n-cnt_tot[arr[i]])
ans = ans * full

other = 0
for i in range(n):
    other += sum2(arr[i]+1,2004)
    add(arr[i],1)
other = other * k

ans += other

ans = ans % mod

print(ans)

Solution (Python):
n, k = map(int, input().split())
L = list(map(int, input().split()))
d = {}
Lsorted = sorted(L)
for i in range(n):
    idx = Lsorted.index(L[i])
    bigger = len([b for b in L[i:] if b<L[i]])
    d[i] = [bigger,idx]


res = 0
for key in d:
    [x, y] = d[key]
    res += x*k + y*k*(k-1)//2
print(res % (10**9 + 7))