Problem:
 Score : 300 points    Problem Statement We have a sequence of N integers A~=~A_0,~A_1,~...,~A_{N - 1} .  Let B be a sequence of K \times N integers obtained by concatenating K copies of A . For example, if A~=~1,~3,~2 and K~=~2 , B~=~1,~3,~2,~1,~3,~2 .  Find the inversion number of B , modulo 10^9 + 7 .  Here the inversion number of B is defined as the number of ordered pairs of integers (i,~j)~(0 \leq i < j \leq K \times N - 1) such that B_i > B_j .      Constraints  All values in input are integers.  1 \leq N \leq 2000  1 \leq K \leq 10^9  1 \leq A_i \leq 2000         Input Input is given from Standard Input in the following format:  N  K  A_0  A_1  ...  A_{N - 1}       Output Print the inversion number of B , modulo 10^9 + 7 .        Sample Input 1 2 2
2 1      Sample Output 1 3  In this case, B~=~2,~1,~2,~1 . We have:   B_0 > B_1  B_0 > B_3  B_2 > B_3   Thus, the inversion number of B is 3 .       Sample Input 2 3 5
1 1 1      Sample Output 2 0  A may contain multiple occurrences of the same number.       Sample Input 3 10 998244353
10 9 8 7 5 6 3 4 2 1      Sample Output 3 185297239  Be sure to print the output modulo 10^9 + 7 .

Solution (Python):
N,K=map(int,input().split())
A = list(map(int, input().split()))
t=0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i]>A[j]:
            t+=1
A.sort()
T=0
s=A[0]
n=0
for i in range(1,N):
    if A[i]!=s:
        n=i
        s=A[i]
    T+=n
print((t*K+K*(K-1)//2*T)%(10**9+7))

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

a = 0
b = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    if A[i] > A[j]:
      a += 1
    if A[i] < A[j]:
      b += 1
ans = a * K * (K + 1) // 2
ans += b * K * (K - 1) // 2
print(ans % MOD)

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

first_count = 0
second_count = 0
for i in range(N):
  for j in range(i, N):
    if a[i] > a[j]:
      first_count += 1
    if a[N-i-1] > a[N-j-1]:
      second_count += 1
      
      
print((first_count * K * (K + 1) // 2 + second_count * K * (K -1) // 2) % (10 ** 9 + 7))

Solution (Python):
M = 10**9+7
n, k = map(int, input().split())
*a, = map(int, input().split())
a = a[::-1]
b = [0]*2001
c = [0]*n
d = [0]*n
for i in range(n):
    b[a[i]] += 1
    if i > 0:
        c[i] += sum(b[:a[i]])
for i in range(n):
    f = b[:a[i]]
    if f: d[i] += sum(f)
g, h = sum(c)%M, sum(d)%M
print((k*g+k*(k-1)//2*h)%M)

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

cnt = [0]*N

for i in range(N):
    c = 0
    x = A[i]
    for j in range(i+1,N):
        y = A[j]
        if x > y:
            c += 1
    cnt[i] = c*K
for i in range(N):
    x = A[i]
    c = 0
    for j in range(N):
        y = A[j]
        if x > y:
            c += 1
    cnt[i] += (c*K*(K-1)//2)%INF
print(sum(cnt)%INF)

Solution (Python):
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = 1000000007

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

print(ans)

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

ans=0

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

print(ans)

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


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

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

s=inside*K+outside*((K*(K-1))//2)

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

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ato=[]
zen=[]
for i in range(n):
    now=a[i]
    temp=0
    if(i!=n-1):
        for j in range(i+1,n):
            if(now>a[j]):
                temp+=1
    ato.append(temp)
    temp=0
    for j in range(n):
        if(a[j]>a[i]):
            temp+=1
    zen.append(temp)




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

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

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

ca_inner *= K
ca_outer *= (K - 1) * K // 2

print((ca_inner + ca_outer) % (10**9 + 7))

Solution (Python):

def solve():
    N,K = map(int, input().split())
    *A, = map(int, input().split())
    L = [0 for i in range(2001)]
    invertion = 0
    for a in A:
        invertion += sum(L[a+1:])
        L[a]+=1
    res = (K*invertion + sum(sum(L[a+1:])*(K*(K-1)//2) for a in A))%(10**9+7)

    return str(res)

if __name__ == '__main__':
    print(solve())

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
No=2**12
tree=[0]*(2*No)
ans=0
def add(k,x):
    k+=No-1
    while k>=0:
        tree[k]+=x
        k=(k-1)//2
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=0
    while L<=R:
        if R&1:
            s+=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s+=tree[L]
        L>>=1;R>>=1
    return s
for i in a:
    ans+=query(i+1,2001)
    ans%=mod
    add(i,1)
import collections
c=collections.Counter(a)
l=sorted(c.items())
t=l[0][1]
ans*=k
ans%=mod
for i,j in l[1:]:
    ans+=j*t*k*(k-1)//2
    ans%=mod
    t+=j
print(ans)

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
a = inl()
x = 0
for i in range(n-1):
    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
print((k*x+k*(k-1)*y//2)%R)

Solution (Python):
import bisect

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

z = [0 for i in range(n)]
r = [0 for i in range(n)]

s = []
for i in range(len(a)):
    idx = bisect.bisect_left(s,a[len(a)-1-i])
    r[len(a)-1-i] = idx
    s.insert(idx,a[len(a)-1-i])
for i in range(n):
    z[i] = bisect.bisect_left(s,a[i])

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

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

mod = 10**9+7

ans = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i]>A[j]:
            ans += 1
            ans %= mod
ans = ans*K%mod
C = {}
for a in A:
    C[a] = C.get(a,0)+1
C2 = [N-C[a] for a in A]
ans2 = K*(K-1)*sum(C2)//4%mod
ans = (ans+ans2)%mod
print(ans)

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

n,k = (int(num) for num in input().split())
a = [int(num) for num in input().split()]
cnt_in = 0
for i in range(n):
    for j in range(i+1,n):
        if a[i] > a[j]:
            cnt_in += 1
dic = {}
for num in a:
    if num not in dic.keys():
        dic[num] = 1
    else:
        dic[num] += 1

        
dic = sorted(dic.items(), key = lambda x:x[0])

cnt_out = 0
v = [item[1] for item in dic]

lv = len(v)
for i in range(lv):
    for j in range(i+1,lv):
        cnt_out += v[i] * v[j]
        
ans = int(cnt_in*k + k*(k-1)//2*cnt_out) % MOD
print(ans)

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

total=me*k+right*(((k-1)*k)//2)
print(total%(10**9+7))

Solution (Python):

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

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

ans = 0
oneloop = 0
base = [0] * 2001

num = [0] * 2001


for i in range(N):

    na = A[i]

    oneloop += num[na]

    for j in range(na):

        num[j] += 1


ans += oneloop * K




for i in range(N):

    na = A[i]
    ans = ( ans + num[na] * K * (K-1) // 2 ) % (10 ** 9 + 7)

print (ans)

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

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

afters = [0]*N
alls = [0]*N

for i, key in enumerate(A):
    for j, a in enumerate(A):
        if a < key:
            alls[i] += 1
            if j > i:
                afters[i] += 1

ans = sum(afters)*K + sum(alls)*K*(K-1)//2
print(ans % D)

Solution (Python):
import itertools

MOD = 10 ** 9 + 7

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

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

counts = [0] * 2000
for a in a_list:
    a -= 1
    counts[a] += 1

accum = list(itertools.accumulate(counts))
for a in a_list:
    a -= 1
    if a == 0:
        continue
    ans += accum[a - 1] * K * (K - 1) // 2
    ans %= MOD
print(ans)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
v=[[0]*N for i in range(2)]
for i,a in enumerate(A):
    for j,aa in enumerate(A):
        if a>aa:
            if i<j:
                v[0][i]+=1
            elif i>j:
                v[1][i]+=1
r=0
m=10**9+7
for i in range(N):
    r+=((v[0][i]*K*(K+1)//2)%m+(v[1][i]*K*(K-1)//2)%m)%m
print(r%m)

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

accum = [0] * n
adding = [0] * n

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

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

MOD = 10**9 + 7
sum_accum = sum(accum)
sum_adding = sum(adding)
ans = 0

ans = (((k-1) * k) // 2) * sum_accum + k * sum_adding
ans %= MOD
'''
for i in range(k):
    ans += sum_accum * i + sum_adding
    ans %= MOD
'''
print(ans)

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

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

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



out = 0

for p in range(n):
    for q in range(n):
        if a[p] < a[q]:
            out += 1



outcount = out * (k * (k-1)) //2

print((incount * k + outcount) % MOD)

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

def main():
    N,K = map(int,input().split())
    A = [int(a) for a in input().split()]
    inversion_in_L = [0]*N
    inversion_in_R = [0]*N
    for i in range(N):
        for j in range(N):
            if j<i and A[j]>A[i]:
                inversion_in_L[i] += 1
            elif i<j and A[j]>A[i]:
                inversion_in_R[i] += 1
    ans = 0
    for i in range(N):
        ans += (K-1)*K*inversion_in_R[i]//2
        ans %= ModNum
        ans += (K+1)*K*inversion_in_L[i]//2
        ans %= ModNum

    print(ans)



if __name__ == "__main__":
    main()

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

inv2 = pow(2,MOD-2,MOD)

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

M1 = (((K*(K-1) % MOD)*inv2) % MOD) + K
M2 = ((K*(K-1) % MOD) * inv2) % MOD

ans = (M1*left + M2 * right) % MOD
print(ans)

Solution (Python):
import sys

lines = sys.stdin.readlines()
parts = lines[0].split(' ')
n = int(parts[0])
k = int(parts[1])
arr = [int(s) for s in lines[1].strip().split()]

ans = 0
mod = 1000000007

for i in range(n):
    in_arr = 0
    all_arr = 0
    for j in range(n):
        if arr[i] > arr[j]:
            all_arr += 1
            if j > i:
                in_arr += 1

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

print(ans)

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

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

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

numInvs = [0] * N
for i, Ai in enumerate(As):
    for Aj in As[i+1:]:
        if Ai > Aj:
            numInvs[i] += 1

nums = [0] * N
for i, Ai in enumerate(As):
    for Aj in As:
        if Ai > Aj:
            nums[i] += 1

ans = 0
for numInv, num in zip(numInvs, nums):
    ans += numInv*K % MOD
    ans += num*K*(K-1)//2 % MOD
    ans %= MOD

print(ans)

Solution (Python):

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

d = {}
for a in al:
    if a not in d:
        d[a] = 0
    d[a] += 1

res = 0
for i in range(n-1):
    for j in range(i+1,n):
        if al[i]>al[j]:
            res += 1
            res %= MOD
res = res*k
res %= MOD

for i in range(n):
    r = 0
    for key in d:
        if al[i]>key:
            r += d[key]
    res += r*k*(k-1)//2
    res %= MOD

print(res)

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

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

Solution (Python):
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=sorted(a)
shokou=[]
kousa=[]
m=10**9+7
for i in range(n):
  ct=0
  for j in range(i+1,n):
    if a[i]>a[j]:ct+=1
  shokou.append(ct)
for i in range(n):
  kousa.append(A.index(a[i]))
ans=0
S=0
for i in range(n):
  S=(k*(2*shokou[i]+(k-1)*kousa[i]))//2
  S%=m
  ans+=S
print(ans%m)

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):
n,k = map(int,input().split())
a = list(map(int,input().split()))
inside = 0
for i in range(n):
  for j in range(i+1,n):
    if a[i] > a[j]:
      inside += 1
inside *= k
mod = 10**9+7
a.sort()
b = [0]
for i in range(1,n):
  if a[i-1] == a[i]:
    b.append(b[-1])
  else:
    b.append(i)
outside = sum(b)
kk = k * (k-1) // 2
kk %= mod
outside *= kk
outside %= mod
ans = (inside + outside) % mod
print(ans)

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

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









ans = 0
pre = []
from bisect import *
for i in range(N):
    a = a_list[i]
    for j in range(i + 1, N):
        b = a_list[j]
        if a > b:
            ans += (K + 1) * K // 2
            ans %= mod
    idx = bisect_left(pre, a)
    ans += idx * ((K-1)*K//2)
    ans %= mod
    insort_left(pre, a)
print(ans)

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

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

total = count1 * k + count2 * k * (k - 1) // 2
print(total % (10 ** 9 + 7))

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-1):
    for j in range(i+1,N):
        if A[i] > A[j]:
            ans += 1
ans *= K

from collections import Counter
ctr = Counter(A)

P = (K*(K-1)//2) % MOD

s = 0
for k,v in sorted(ctr.items()):
    tmp = (v*s*P)%MOD
    ans += tmp
    ans %= MOD
    s += v

print(ans)

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

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


def count_inversions(li, max=None):
    if not max:
        max = __builtins__.max(li)
    bit = BinaryIndexedTree(size=max + 1)
    ret = 0
    for i in range(len(li)):
        ret += i - bit.sum(li[i])
        bit.add(li[i], 1)
    return ret


N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))

bit = BinaryIndexedTree(size=2001)
invs = []
for i, a in enumerate(A):
    invs.append(i - bit.sum(a))
    bit.add(a, 1)
ans = 0
for i, a in enumerate(A):
    rem = N - bit.sum(a)
    ans += K * (2 * invs[i] + (K - 1) * rem) // 2
    ans %= MOD
print(ans)

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

cnt = [0] * 2001
for i in range(n):
    cnt[a[i]] += 1

ruiseki = [0] * (2000 + 1 + 1)
for i in range(2000 + 1):
    ruiseki[i+1] = ruiseki[i] + cnt[i]

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

Solution (Python):
mod = 10**9+7
N,K=map(int,input().split())
A = [int(i) for i in input().split()]

tento = []
ookii = []
for i,a in enumerate(A):
  te=0
  oo=0
  for j,b in enumerate(A):
    if j==i:continue
    if b>a:
      oo+=1
      if j<i:
        te+=1
  tento.append(te)
  ookii.append(oo)
Tent = sum(tento)%mod
Lar = sum(ookii)%mod
L = Lar *K*(K-1)//2
R = Tent*K

print((L+R)%mod)

Solution (Python):
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
mod = 7 + 10 ** 9
Atype = set(A)

mult = K * (K - 1)// 2
mult %= mod

count = dict()
for a in A:
    if a in count: count[a] += 1
    else: count[a] = 1

inside = 0
used = dict()
used[A[N-1]] = 1
for i in reversed(range(N-1)):
    for k in used:
        if A[i] > k: inside += used[k]
    if A[i] in used: used[A[i]] += 1
    else: used[A[i]] = 1
inside *= K
inside %= mod

after = 0
for a in A:
    for k in count:
        if a > k: after += count[k]
after *= mult
after %= mod

print((inside + after) % mod)

Solution (Python):
n,k = map(int,input().split())
A = list(map(int,input().split()))
p = []
B = sorted(A)
for i in range(n):
    cnt = 0
    for j in range(i+1, n):
        if A[i] > A[j]:
            cnt += 1
    p.append(cnt)

ans = 0
mod = 10**9 + 7
for i,a in enumerate(A):
    ans = (ans + (k-1) * k * B.index(a) // 2 + p[i]*k) % mod
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

ans = 0

MOD = 10**9+7
for i, a in enumerate(A):
    bef = 0
    aft = 0
    for j, b in enumerate(A):
        if a > b:
            if i > j:
                aft += 1
            else:
                bef += 1
    ans += bef*(K*(K+1))//2
    ans += aft*(K*(K-1))//2
    ans %= MOD
print(ans)

Solution (Python):
import sys, math, itertools, bisect, copy, re

from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint


input = sys.stdin.readline

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)








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

T1 = [0] * N
T2 = [0] * N

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

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

ans = sum(T1) * K
ans %= MOD
ans += sum(T2) * K * (K - 1) // 2
ans %= MOD

print(ans)

Solution (Python):
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
tentosu1=0
mod=10**9+7
for i in range(N):
    for j in range(N):
        if i<j and A[i]>A[j]:
            tentosu1+=1
tentosu1%=mod
D=dict()
for i in range(N):
    if A[i] in D:
        D[A[i]]+=1
    else:
        D[A[i]]=1
difftento=0
S=(K*(K-1))//2
S%=mod
for i in D:
    for j in D:
        if i>=j:
            continue
        difftento+=S*D[i]*D[j]
        difftento%=mod
print((((tentosu1*K)%mod)+difftento)%mod)

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

cnt_a = 0
cnt_b = 0
for i in range(n-1):
    for j in range(i+1,n):
        cnt_a += 1 if a[i] > a[j] else 0
        cnt_b += 1 if a[i] < a[j] else 0
ans = cnt_a * (1+k)*k//2
ans += cnt_b * (1+k-1)*(k-1)//2


print(ans%MOD)

Solution (Python):

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret



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

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

S_tag = [0]*2001

for i in range(N):
        S_tag[A[i]]+=1

bit=BIT([0]*2001)

bit.add(A[0],1)
count = 0

for i in range(1,N):
        count+=bit.sum(2000)-bit.sum(A[i])
        bit.add(A[i],1)

mod = 10**9 + 7

ans = 0
for i in range(1,2001):
        ans += bit.sum(i-1)*S_tag[i]

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

ans += K*count
ans %= mod

print(ans)

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

from collections import defaultdict
from itertools import combinations

d = defaultdict(int)

k = 0
K %= mod

for i,j in combinations(range(N),2):
    if A[i] > A[j]:
        k+=1
        d[A[j]]+=1
    elif A[j] > A[i]:
        d[A[i]]+=1

ans = (k * K) % mod

for k in d.keys():
    ans += d[k]*(K*(K-1)//2) % mod
    ans %= mod

print(ans)

Solution (Python):
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, K = inpl()
A = inpl()
correct = 0
inverse = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] < A[j]:
            correct += 1
        elif A[i] > A[j]:
            inverse += 1

W1 = K*(K-1)//2 % MOD
W2 = K*(K+1)//2 % MOD
ans = (correct*W1+inverse*W2) % MOD
print(ans)

Solution (Python):
from collections import Counter
mod = 1000000007


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


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

def main():
    n, k=map(int, input().split())
    a = list(map(int, input().split()))
    ans = bubble_sort(a) * k % mod
    div2 = inverse(2)
    
    lft = 0
    rgt = 0
    while lft < n:
        while rgt < n and a[lft] == a[rgt]:
            rgt += 1
        ans = (ans + (rgt - lft) * (n - rgt) % mod * k % mod * (k-1) * div2 % mod) % mod
        lft =rgt

    print(ans)
main()

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

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


B0=[]

for i in range(N):
    ANS=0
    k=A[i]
    for j in range(i+1,N):
        if A[j]<k:
            ANS+=1

    B0.append(ANS)

count=[0]*(max(A)+1)

for a in A:
    count[a]+=1

from itertools import accumulate
S=list(accumulate(count))

ANS=0

for i in range(N):
    t=S[A[i]-1]
    ANS=(ANS+B0[i]*K+t*K*(K-1)//2)%mod

print(ANS)

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

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

KR=((K*(1+K))//2)%MOD
KL=(((K-1)*K)//2)%MOD

ans=0
for i in range(N):
    ans = (ans + (KR*R[i])%MOD)%MOD
    ans = (ans + (KL*L[i])%MOD)%MOD
print(ans)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools


def main():
    nun, k = map(int, input().split())
    data = list(map(int, input().split()))

    aaa = [0 for i in range(nun)]
    for i in range(nun):
        for j in range(nun):
            if i == j:
                continue
            if data[i] > data[j]:
                aaa[i] += 1

    mod = 10 ** 9 + 7
    ans = 0
    
    for i in range(nun):
        shokou = 0
        for j in range(i + 1, nun):
            if data[i] > data[j]:
                
                shokou += 1
        
        ans += (shokou + shokou + (k - 1) * aaa[i]) * k // 2
        
        ans %= mod

    print(ans)





if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
n,k = map(int,input().split())
arr = list(map(int,input().split()))

base = 0
mod = 10**9 + 7
mul = (k*(k+1))//2
mul2 = (k*(k-1))//2

for i in range(n):
    for j in range(i):
        if arr[i] < arr[j]:
            base += 1
    

pot = 0
for i in range(n):
    for j in range(i+1,n):
        if arr[i] < arr[j]:
            pot += 1





print((base*mul+pot*mul2)%mod)

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    div = pow(10, 9) + 7

    pairs1 = []
    pairs2 = []
    for i in range(N):
        ref = A[i]
        count1 = 0
        count2 = 0
        for j in range(N):
            if j < i and A[j] < ref:
                count2 += 1
            elif j > i and A[j] < ref:
                count1 += 1
        count2 += count1
        pairs1.append(count1)
        pairs2.append(count2)

    
    
    
    ans = 0
    for i in range(N):
        ans += pairs1[i]*K % div
        ans += pairs2[i]*K*(K-1)//2 % div
    return ans % div

if __name__ == '__main__':

    print(main())

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

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

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

        if a < b:
            total += k * (k-1) // 2
            total %= mod
        if a > b:
            total += k * (k+1) // 2
            total %= mod

print(total)

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

ans = 0

for i, a in enumerate(A):
    big_mae = 0
    big_ushiro = 0
    for j in range(i):
        if A[j] < a:
            big_mae += 1
    for j in range(i + 1, N):
        if A[j] < a:
            big_ushiro += 1
    
    

    ans += big_ushiro*K + (big_mae + big_ushiro)*K*(K-1)//2
    ans %= 1000000007

print(ans)

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

mod = int(1E9+7)

C = []
for i in range(N-1):
    a = A[i]
    p = 0
    for j in range(i+1, N):
        if A[j] < a:
            p += 1
    C.append(p)
C.append(0)

D = []
for i in range(N):
    a = A[i]
    q = 0
    for j in range(N):
        if A[j] < a:
            q += 1
    D.append(q)

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

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

k = k%1000000007

tent  = [0 for i in range(n)]
ind = [0 for i in range(n)]

for i in range(n):
        al = 0
        bl = 0
        for j in range(n):
                if i < j and a[i] > a[j]:
                        al += 1
                if a[i] > a[j]:
                        bl += 1

        tent[i] = al
        ind[i] = bl




ans = 0

for i in range(n):
        ans += tent[i]*k
        ans +=(k*(k-1)//2)*ind[i]
        
        ans = ans%1000000007
print(ans%1000000007)

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

l=[]
l2=[]
for i in range(n):
    temp=0
    temp2=0
    for j in range(n):
        if a[i]>a[j]:
            if i<j:
                temp2+=1
            temp+=1
    l.append(temp)
    l2.append(temp2)
ans=0
for i in range(n):
    ans=(ans+k*l2[i]+(((k-1)*k*l[i]))//2)%(10**9+7)
print(ans)

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

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

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

if K == 1:
    print(c)
elif K == 2:
    print(c * 2 + cp)
else:
    print((c * K + (K * (K - 1) // 2) * cp) % (10 ** 9 + 7))