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

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

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

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

x = ((t)*(k)*(k-1))//2
y = inner*k
print(int((x+y)%mod))

Solution (Python):
from collections import defaultdict

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

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

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

x = (t*k*(k-1))//2
y = inner*k
print(int((x+y)%mod))

Solution (Python):
from collections import defaultdict
d = defaultdict(int)

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

inner = 0
for i in range(N):
  d[A[i]] += 1
  for j in range(i+1, N):
    if A[i] > A[j]:
      inner += 1
inner *= K

d = sorted(d.items())
outer = 0
cnt = d[0][1]
for k, v in d[1:]:
  outer += cnt * v
  cnt += v
outer *= K*(K-1)//2

print((inner + outer)%(10**9+7))

Solution (Python):
N,K = map(int, input().split())
A = list(map(int,input().split()))
t = 0
for i in range(N-1):
  for j in range(N-i-1):
    if A[i] > A[j+i+1]:
      t += 1
u = 0
for i in range(N):
  for j in range(N):
    if A[i]>A[j]:
      u += 1
T = t%(10**9+7)
U = u%(10**9+7)
Z=K*(K-1)//2%(10**9+7)
Y=T*K%(10**9+7)
X=U*Z%(10**9+7)
ans = (Y+X)%(10**9+7)
print(ans)

Solution (Python):
N,K = map(int, input().split())
A = list(map(int,input().split()))
t = 0
for i in range(N-1):
  for j in range(N-i-1):
    if A[i] > A[j+i+1]:
      t += 1
u = 0
for i in range(N):
  for j in range(N):
    if A[i]>A[j]:
      u += 1
T = t%(10**9+7)
U = u%(10**9+7)
Z=K*(K-1)//2%(10**9+7)
Y=T*K%(10**9+7)
X=U*Z%(10**9+7)
ans = (Y+X)%(10**9+7)
   
print(ans)

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

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

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

print(ans)

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]:
      b += 1
    elif A[i] > A[j]:
      a += 1
ans = a*(K*(K+1))//2 + b * (K*(K-1))//2
ans = ans % (10**9 + 7)
print(ans)

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7


N, K = MAP()

A = LIST()

whole = [0]*N
first = [0]*N

for i in range(N):
	for j in range(N):
		if A[j] < A[i]:
			whole[i] += 1
			if i < j:
				first[i] += 1

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

print(ans%mod)

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

Solution (Python):
from decimal import Decimal

N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10 ** 9 + 7
ans = 0
cnt = 0

def tosa(a,n,d):
    s = Decimal(n / 2) * (2*a+(n-1)*d)
    return int(s)

if N == 1:
    print(ans)
    exit()

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

d = N*(N-1)//2
print(tosa(ans,K,d-cnt)%mod)

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


from functools import lru_cache


def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 10**9+7
    

    
    N, K = map(int, input().split())
    A = tuple(map(int, input().split())) 
    
    
    count=0
    la=len(A)
    for i in range(0,la-1):
        for j in range(i+1,la):
            ai,aj=A[i],A[j]
            if ai>aj:
                count+=1
    
    asrt=sorted(list(A))
    d=dict()

    rui=0
    for i,a in enumerate(asrt):
        if a in d:
            continue
        else:
            d[a]=i

    ans=(count*K)%mod
    
    for a in A:
        order=d[a]
        ans=(ans+((K*(K-1)//2)%mod*order)%mod)%mod

    print(ans)

if __name__ == "__main__":
    main()

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

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N,K = IL()
A = IL()
count = 0
for i in range(N):
  for j in range(i+1,N):
    if A[i]>A[j]:
      count += 1
count2 = 0
for i in range(N):
  for j in range(N):
    if A[i]>A[j]:
      count2 += 1
print(((count*K)+(count2*(K-1)*K//2))%MOD)

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

def solve():
    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)
        
    return ans % MOD
    
print(solve())

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

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

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

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

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


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

Solution (Python):






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





ans1 = 0
ans2 = 0
for i,a in enumerate(A):
    for j,a_ in enumerate(A):
        if i > j:
            if a > a_:
                ans2 += 1
        if i < j:
            if a > a_:
                ans1 += 1
                ans2 += 1
print((ans1*K + ans2*(K*(K-1)//2))%(10**9+7))

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

num1 = 0
num2 = 0

for i in range(N):
    for j in range(N):
        if i > j:
            if l[i] > l[j]:
                num2 += 1
        if j > i:
            if l[i] > l[j]:
                num1 += 1
                num2 += 1

print((num1 * K + num2 * (K*(K-1)//2)) % (10**9 + 7))

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

Solution (Python):
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(i + 1, n):
        if a[i] > a[j]:
            cnt1 += 1

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

Solution (Python):
from sys import stdin
n,k = map(int,stdin.readline().rstrip().split())
li = list(map(int,stdin.readline().rstrip().split()))
nai = 0
ato = 0
point = 0
for i in range(n):
    for s in range(i+1,n):
        if li[i] > li[s]:
            nai += 1
    for v in range(n):
        if li[i] > li[v]:
            ato += 1
point += (nai*k)+(ato*k*(k-1)//2)
print(point%(10**9+7))

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

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

cnt_each=0
for i in A:
  for j in A:
    if i>j:
      cnt_each +=1

cnt_A = (K*cnt_self)%p
cnt_B = ((K*(K-1)//2)*cnt_each)%p
ans = (cnt_A+cnt_B)%p


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):
  f,g = 0,0
  for j in range(N):
    if A[i] > A[j]:
      g += 1
      if i < j:
        f += 1
  ans += ((f*K)+(g*(K*(K-1)//2)))%mod
print(ans%mod)

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

Solution (Python):
def inversion(A,N,K,M):
    B = [0 for _ in range(N)]
    C = [0 for _ in range(N)]
    
    
    for i in range(N):
        for j in range(i+1,N):
            if A[i] > A[j]:
                B[i] += 1

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

    output = sum(B) * K
    output += sum(C) * K * (K-1) //2
    output %= M

    return output

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    M = 10**9+7

    print(inversion(A,N,K,M))

if __name__ == "__main__":
    main()

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

invs = []
for idx in range(n):
    result = [0,0]
    for idx2 in range(n):
        if idx2 < idx:
            loc = 1
        elif idx2 > idx:
            loc = 0
        else:
            continue
        if data[idx2] < data[idx]:
            result[loc] += 1
    invs.append(result)
ans = 0
for aft, bef in invs:
    ans += aft*k
    m = (bef+aft)*(k-1)
    ans += (m*k)//2
print(ans%mod)

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


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


from collections import Counter
ca = Counter(a)

c2 = 0
for n1,cnt1 in ca.items():
    for n2,cnt2 in ca.items():
        if n2<n1:
            c2+=cnt2*cnt1

MOD=10**9+7
k %= MOD
ans = (c1*k)%MOD + (c2*k*(k-1)//2)%MOD
ans %= MOD
print(ans)

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

Solution (Python):

"""
Created on Sun May 31 11:25:07 2020

@author: NEC-PCuser
"""

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

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

tentosu = 0

MOD = 1000000007

for i in range(0, N):
    a = 0
    d = 0
    """
    for j in range(0, N):
        if (i == j):
            continue
        if (i < j and A[i] > A[j]):
            a += 1
        if (A[i] > A[j]):
            d += 1
    """
    for j in range(0, N):
        if (A[i] > A[j]):
            d += 1
    for j in range(i, N):
        if (A[i] > A[j]):
            a += 1
    
    
    tentosu += a * K + (K - 1) * K * d // 2;
    
print(tentosu % MOD)

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

ans = 0
tmp = 0
tmp2 = 0
for i in range(N):
    for j in range(i):
        if A[i] < A[j]:
            tmp += 1
    for j in range(N):
        if A[i] > A[j]:
            tmp2 += 1

k = (K * (K-1) // 2) % mod
ans = ans + (tmp * K % mod) + (tmp2 * k % mod)
print(ans % mod)

Solution (Python):
from collections import Counter
from itertools import combinations
n, k = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7
inv_num = 0
for left, right in combinations(A, 2):
    if left > right:
        inv_num += 1


acc_num = 0
counter = Counter(A)
rest = n
for key in sorted(counter.keys(), reverse=True):
    rest -= counter[key]
    acc_num += rest * counter[key]

total = (inv_num * k) % mod
total += ((acc_num % mod) * ((k * (k - 1) // 2) % mod)) % mod
total %= mod
print(total)

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):
    cnt = 0
    cnt2 = 0
    for j in range(n):
        if a[i] > a[j]:
            cnt += 1
            if i < j:
                cnt2 += 1
    ans += (cnt*(k-1)*k//2 % mod) + cnt2*k
    ans %= mod
    
print(ans)

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

ans = 0
tmp = 0
tmp2 = 0
for i in range(N):
    for j in range(i):
        if A[i] < A[j]:
            tmp += 1
    for j in range(N):
        if A[i] > A[j]:
            tmp2 += 1

k = (K * (K-1) // 2) % mod
ans = ans + (tmp * K % mod) + (tmp2 * k % mod)
print(ans % mod)

Solution (Python):
N, K = map(int, input().split())
mod = 10**9+7
A = list(map(int,input().split()))
cnt1 = 0
cnt2 = 0
for i in range(N):
    for k in range(N):
        if A[i] > A[k]:
            if i+1 <= k < N:
                cnt1 += 1
                cnt2 += 1
            else:
                cnt2 += 1
            cnt1 %= mod
            cnt2 %= mod

ans = (cnt1 * K + cnt2 * (K-1)*K // 2) % mod
print(ans)

Solution (Python):
N,k = map(int,input().split())
A = 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[i] > A[j]:
            ans += k*(k+1)//2
        elif A[i] < A[j]:
            ans += k*(k-1)//2

        ans %= MOD

print(ans)

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

Solution (Python):
def answer(arr, k):
    _mod = (10**9+7)
    left = 0
    right = 0
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if arr[i] > arr[j]:
                left += 1
            if arr[i] < arr[j]:
                right += 1
    
    left = (left * (k*(k+1))//2)
    right = (right * (k*(k-1))//2)
    return int((left+right)%_mod)
    
n, k = map(int, input().split())
arr = list(map(int, input().split()))
print(answer(arr, k))

Solution (Python):
import bisect
N, K = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9 + 7
ans = 0
a.reverse()
lst2 = sorted(a)
memo = {}
for i in range(N):
    if not a[i] in memo:
        memo[a[i]] = bisect.bisect_left(lst2, a[i])
    ans += K * (K - 1) // 2 *memo[a[i]]

for i in range(1, N):
    lst = sorted(a[0:i])
    k1 = bisect.bisect_left(lst, a[i])
    ans += k1 * K
    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):
    for j in range(N):
        if A[i] > A[j]:
            if i > j:
                ans += k*(k-1)//2
            elif i < j:
                ans += k*(k+1)//2
            ans %= MOD

print(ans)

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

mod = 10**9 + 7
result = 0
count = [0] * 2001


for a in A:
    count[a-1] += 1
    result += K * sum(count[a:])
    result %= mod

kn = 0

count = [i for i in count if i != 0]
total = sum(count) % mod

for i in count:
    total -= i
    kn += total * i
    kn %= mod

result += kn * K*(K-1)//2
result %= 10**9 + 7

print(result)

Solution (Python):

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

EPS = 10**9 + 7

cnt = 0

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

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

result = cnt * k + soto

print(result % EPS)

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

    mod = 10 ** 9 + 7

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

        ans += tmp_2 * K * (K+1) // 2
        ans += (tmp_1-tmp_2) * (K-1) * K // 2
        ans %= mod

    print(ans)


if __name__ == "__main__":
    main()

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

'''
k=4,a_input=[5,2,4,1]の場合を考える
5 2 4 1 5 2 4 1 5 2 4 1 5 2 4 1 

例えば、4に着目すると
5 2 [4] <1> |5 <2> 4 <1> |5 <2> 4 <1> |5 <2> 4 <1>
1 + 2 + 2 + 2
1 + 2 + 2
1 + 2
1 + 0
で総数を求めることができる
左側の1は(a内の右側でa_i>a_jの個数)*k

それ以外は等差数列の和として
(初項+最終項)*項数/2
= n*(k-1)*k/2
で求めることができる

あとは各数字ごとにこれを足し合わせる
'''
ans=0
for i in range(n):
    tmp1=0
    tmp2=0
    for j in range(n):
        if i==j:
            continue
        if j>=i+1:
            if a_input[i]>a_input[j]:
                tmp1+=1
        if a_input[i]>a_input[j]:
            tmp2+=1
    ans+=tmp1*k
    ans+=tmp2*(k-1)*k//2
print(ans%(10**9+7))

Solution (Python):
import numpy as np

n, k = map(int, input().split())
arr = np.array(list(map(int, input().split())))


a = 0
for i in range(n - 1):
    a += np.where(arr[i + 1:] < arr[i])[0].shape[0]


d = 0
for i in range(n):
    d += np.where(arr < arr[i])[0].shape[0]

mod = 10**9 + 7

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

print(ans)

Solution (Python):
import numpy as np

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


start = 0
for i in range(n - 1):
    start += np.where(a[i + 1:] < a[i])[0].shape[0]


coef = 0
for i in range(n):
    coef += np.where(a < a[i])[0].shape[0]

mod = 10**9 + 7

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

print(ans)

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

same = 0
for i, ei in enumerate(a):
    for j, ej in enumerate(a[i+1:], i + 1):
        if ei > ej:
            same += 1
            same %= mod

other = 0
for ei in a:
    for ej in a:
        if ei > ej:
            other += 1
            other %= mod

ans = same * k + other * k * (k - 1) // 2
ans %= mod
print(ans)

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

micro=0
for i in range(N):
    for j in range(i):
        if A[i]<A[j]:
            micro+=1
A.sort()
macro=[0]
for i in range(1,N):
    if A[i-1]==A[i]:
        macro.append(macro[-1])
    else:
        macro.append(i)

ans=(micro*K+sum(macro)*K*(K-1)//2)%mod
print(ans)

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

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


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


ini = 0
for k in range(N):
    for l in range(N):
        if A[k] > A[l]:
            ini += 1
ini = ini * K * (K-1) // 2
ans = (inv+ini) % INF
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):
    migi = 0
    a = A[i]
    for j in range(i+1,n):
        if a > A[j]:
            migi += 1
    ans += migi * k
    ans %= mod

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

Solution (Python):
import sys, re
from math import ceil, floor, sqrt, pi, factorial
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def mod_cmb(n: int, k: int, p: int) -> int:
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if (k > n - k):
        return mod_cmb(n, n - k, p)
    c = d = 1
    for i in range(k):
        c *= (n - i)
        d *= (k - i)
        c %= p
        d %= p
    return c * pow(d, p - 2, p) % p

def main():
    n, k = i_map()
    num_list = i_list()

    first = 0
    second = 0

    for i in range(n):
        for j in range(i+1,n):
            if num_list[i] > num_list[j]:
                first += 1
        for j in range(n):
            if num_list[j] < num_list[i]:
                second += 1
    
    ans = first * k + k * (k-1) * second // 2

    print(ans%MOD)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    MOD = 10 ** 9 + 7
    
    C1 = np.array([0] * n)
    C2 = np.array([0] * n)
    for i in range(n):
        C1[i] = np.count_nonzero(A[i:] < A[i])
        C2[i] = np.count_nonzero(A < A[i])
    c1,c2 = C1.sum(),C2.sum()
    ans = 0
	
    ans += c1 * k % MOD
    ans += c2 * (k * (k - 1) // 2 % MOD)

    print(ans % MOD)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() 
ni = lambda: int(readline().rstrip()) 
nm = lambda: map(int, readline().split()) 
nl = lambda: list(map(int, readline().split())) 

n, k = nm()
values = nl()
a = 0
b = 0

for i, v in enumerate(values):
    tmp_a = 0
    cnt_b = 0
    for j, v_c in enumerate(values):
        if v > v_c:
            tmp_a += 1
            if i > j:
                cnt_b += 1
    tmp_b = tmp_a * k - cnt_b
    a -= tmp_a
    b += tmp_b
    
print((a * k * (k + 1) // 2 + (b - a) * k) % (10 ** 9 + 7))

Solution (Python):
n,k = map(int,input().split())
mod = 10**9+7
a = list(map(int,input().split()))
c = [0]*n
b = []
import bisect
for i in range(n-1,-1,-1):
    c[i] = bisect.bisect_left(b,a[i])
    bisect.insort_left(b,a[i])
    
ans = 0
for i in c:
    ans += i*k

for i in range(n):
    c[i] = bisect.bisect_left(b,a[i])
    
sk = k*(k-1)//2
for i in c:
    ans += i*sk

print(ans%mod)

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

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