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 sys

MOD = 1000000007  

def mergeSortInversions(arr):
    if len(arr) == 1:
        return arr, 0
    else:
        a = arr[:len(arr)//2]
        b = arr[len(arr)//2:]
        a, ai = mergeSortInversions(a)
        b, bi = mergeSortInversions(b)
        c = []
        i = 0
        j = 0
        inversions = 0 + ai + bi
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
            inversions += (len(a)-i)
    c += a[i:]
    c += b[j:]
    return c, inversions

def mergeAndCountSplitInv(c, d):
    
    nc = len(c)
    nd = len(d)
    b = [0] * (nc + nd)
    i, j = 0, 0
    splitInv = 0
    for k in range((nc + nd)):
        if i == nc: 
            b[k] = d[j]
            j += 1
            continue
        if j == nd: 
            b[k] = c[i]
            i += 1
            continue

        if c[i] <= d[j]: 
            b[k] = c[i]
            i += 1
        elif c[i] > d[j]:
            b[k] = d[j]
            splitInv += nc - i
            j += 1
    return b, splitInv

def sortCountInv(a):
    
    n = len(a)
    if n <= 1: 
        return a, 0
    c, leftInv = sortCountInv(a[ : n//2])
    d, rightInv = sortCountInv(a[n//2: ])
    b, splitInv = mergeAndCountSplitInv(c, d)
    
    return b, leftInv + rightInv + splitInv

def solve(N: int, K: int, A: "List[int]"):
    A_sort, inv = mergeSortInversions(A)
    t = [0] * N
    for i in range(1, N):
        if A_sort[i] > A_sort[i-1]:
            t[i] = i
        else:
            t[i] = t[i-1]
    count = inv * K + sum(t) * (K * (K-1))//2
    count = count % MOD
    print(count)
    return


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

if __name__ == '__main__':
    main()

Solution (Python):

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

count1 = 0
count2 = 0
for i in range(N):
    for j in range(i+1, N):
        if j <= K * N - 1 and A_lst[i] > A_lst[j]:
            count1 += 1
    for j in range(N):
        if j <= K * N - 1 and A_lst[i] > A_lst[j]:
            count2 += 1

count2 %= mod

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

ans = count1 * K + count2 * F
ans %= mod

"""
if A_lst[N-1] > A_lst[0]:
    ans -= 1
"""

print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,K = map(int,input().split(' '))
l = list(map(int,input().split(' ')))

u = 10**9 + 7
in_cnt = 0
out_cnt = 0
for i in range(N):
    k = l[i]
    for j in l[i:]:
        if k > j:
            in_cnt += 1
for i in range(N):
    k = l[i]
    for j in range(N):
        kk = l[j]
        if i==j:
            continue
        if k > kk:
            out_cnt += 1
cnt = out_cnt*(K*(K-1)//2)
cnt += in_cnt*K
print(cnt%u)

Solution (Python):
n,k = map(int, input().split())
a = list(map(int,input().split()))
aa = sorted(a)
c = 0
d = 0
for i in range(n):
  c += len([l for l in a[i:] if l < a[i]]) % (10**9+7)
  c = c % (10**9+7)
  d += aa.index(a[i])
  d = d % (10**9+7)
c *= k
K = (0+k-1)*k // 2
c += (d*K) % (10**9+7)
c = c % (10**9+7)
print(c)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)


def solve():
  n,k = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  mod = 10**9+7
  firstt = [0]*n
  for i in range(n-1):
    for j in range(i+1,n):
     if a[i] > a[j]:
      firstt[i] += 1
      
  secondt = [0]*n
  a2 =  a + a
  for i in range(n):
   for j in range(i+1,2*n):
    if a2[i] > a2[j]:
      secondt[i] += 1
  
  query = []
  for i in range(n):
    query.append(secondt[i]-2*firstt[i])

  ans = 0
  for i in range(n):
    tmp = 0
    tmp += (query[i]*(k*(k-1)))
    tmp += (firstt[i]*(k*(k+1)))
    tmp //= 2
    ans += tmp
  print(ans%mod)
solve()

Solution (Python):

import collections

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

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

inner_count = count_inversion(A)

A = sorted(A)

duplicate = {k:1 for k,v in enumerate(A)}

A_index = 0
duplicate_index = 0

while A_index < len(A)- 1:
    if A[A_index+1] == A[A_index]:
        duplicate[A_index + 1] -= 1
        duplicate[duplicate_index] += 1
    else:
        duplicate_index = A_index + 1
    A_index += 1
        
count = 0
for k, v in duplicate.items():
    count += (v * k * K * (K-1) )//2

count += inner_count * K

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

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

M = 10 ** 9 + 7

R = [0] * N
L = [0] * N

for i in range(N):
    Tr = 0
    if i <= N - 2:
        for r in range(i + 1, N):
            if A[i] > A[r]:
                Tr += 1
    Tl = 0
    if i > 0:
        for l in range(i - 1, -1, -1):
            if A[i] > A[l]:
                Tl += 1
    R[i] = Tr
    L[i] = Tl

sum = 0
for i in range(N):
    sum += R[i] * K * (K + 1) // 2 % M + L[i] * (K - 1) * K // 2 % M


print(sum % M)

Solution (Python):
from bisect import bisect_left

N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
B = sorted(A)
for i in range(N):
    for j in range(i + 1, N):
        if A[i] > A[j]:
            ans += 1
ans *= K
S = set(A)
less = [0] * 2000
for s in S:
    less[s - 1] = bisect_left(B, s)
    ans += bisect_left(B, s) * A.count(s) * (K * (K - 1)) // 2
    ans %= 10 ** 9 + 7

print(ans)

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

Solution (Python):

import collections

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

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

inner_count = count_inversion(A)

A = sorted(A)

duplicate = {k:1 for k,v in enumerate(A)}

A_index = 0
duplicate_index = 0

while A_index < len(A)- 1:
    if A[A_index+1] == A[A_index]:
        duplicate[A_index + 1] -= 1
        duplicate[duplicate_index] += 1
    else:
        duplicate_index = A_index + 1
    A_index += 1
        
count = 0
for k, v in duplicate.items():
    count += (v * k * K * (K-1) )//2

count += inner_count * K

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

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

LARGE = 10 ** 9 + 7
res_lr = 0
res_rl = 0

for i in range(N):
    for j in range(N):
        if A_list[i] > A_list[j]:
            if i < j:
                res_lr += 1
            else:
                res_rl += 1

res_1 = (res_lr * K) % LARGE
res_2 = ((res_lr + res_rl) * K * (K - 1) // 2) % LARGE

print((res_1 + res_2) % LARGE)

Solution (Python):
import sys
N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

mod=10**9+7

naka=[ 0 for _ in range(N)]
soto=[ 0 for _ in range(N)]

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

v=0
for i in range(N-1):
	if A[i]<A[i+1]:
		v=i+1
		soto[i+1]=v
	else:
		soto[i+1]=v		


print (sum(naka)*K+sum(soto)*K*(K-1)/2)%mod

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

a_list = [int(a) for a in input().split()]

result_list = [[0,0] for _ in range(N)]
for i in range(N):
    aa = a_list[i]

    f = 0
    for j in range(N):
        an = a_list[j]
        if i == j:
            f = 1
            continue

        if aa > an:
            result_list[i][f] += 1

c = 0
for i, j in result_list:
    kk = i+j
    c += (kk*K*(K+1)//2 - i*K)

n = 1000000000+7

print(c%n)

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

mp = {}

for i in range(20000):
    mp[i] = (0, 0)

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

for i in mp:
    tmp = mp[i][1] * ((k + 1) * k) // 2
    res += tmp
    tmp = mp[i][0] * ((k - 1) * k) // 2
    res += tmp

MOD = 10 ** 9 + 7
print(res % MOD)

Solution (Python):
def main():
    M=10**9+7
    n,k=map(int,input().split())
    r1=k*(k+1)//2%M
    r2=k*(k-1)//2%M
    *a,=map(int,input().split())
    ans=0
    for i,t in enumerate(a):
        tem=0
        for j,u in enumerate(a):
            if u<t:
                if j<i:tem+=r2
                else:tem+=r1
        ans+=tem
        ans%=M
    print(ans)
main()

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


class BinaryIndexedTree:
    """
        Parameters
        ----------
        array : list
            to construct BIT from
        f : func
            binary operation of the abelian group
        fi : func
            inverse mapping of f
            i.e. f(a, b) == c <-> fi(c, a) == b
        e : 
            identity element of the abelian group
        size : int
            limit for array size
    """

    def __init__(self, array, f, fi, e, size):
        self.f = f
        self.fi = fi
        self.e = e
        self.size = size
        self.n = len(array)
        self.dat = [e] * (size + 1)
        self.array = [e] * size
        self.build(array)

    def build(self, array_):
        for i, v in enumerate(array_):
            self.modify(i, v)

    def modify(self, p, v):
        """
        set value at position p (0-indexed)
        """
        self.add(p, self.fi(v, self.array[p]))

    def add(self, p, dv):
        """
        add value at position p (0-indexed)
        """
        fi, dat, f, size, array = self.fi, self.dat, self.f, self.size, self.array
        array[p] = f(array[p], dv)
        p += 1
        while p <= size:
            dat[p] = f(dat[p], dv)
            p += p & -p

    def query(self, l, r):
        """
        result on interval [l, r) (0-indexed)
        """
        return self.fi(self._query(r), self._query(l))

    def _query(self, p):
        dat, f, res = self.dat, self.f, self.e
        while p:
            res = f(res, dat[p])
            p -= p & -p
        return res


f = lambda x, y: x + y
fi = lambda z, x: z - x
e = 0
BIT = BinaryIndexedTree([0] * 2001, f=f, fi=fi, e=e, size=2001)
ans1 = N * (N + 1) // 2
for a in A:
    BIT.add(a, 1)
    ans1 -= BIT._query(a + 1)

BIT = BinaryIndexedTree([0] * 2001, f=f, fi=fi, e=e, size=2001)
ans2 = 2 * N * (2 * N + 1) // 2
for a in A:
    BIT.add(a, 1)
    ans2 -= BIT._query(a + 1)
for a in A:
    BIT.add(a, 1)
    ans2 -= BIT._query(a + 1)

BIT = BinaryIndexedTree([0] * 2001, f=f, fi=fi, e=e, size=2001)
ans3 = 3 * N * (3 * N + 1) // 2
for a in A:
    BIT.add(a, 1)
    ans3 -= BIT._query(a + 1)
for a in A:
    BIT.add(a, 1)
    ans3 -= BIT._query(a + 1)
for a in A:
    BIT.add(a, 1)
    ans3 -= BIT._query(a + 1)

x = ans1
y = ans2
z = ans3
mod = 10**9 + 7
K -= 1
print(((
    (K - 2) * (K - 1) * x - 2 * K * (K - 2) * y + (K - 1) * K * z) // 2) % mod)

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

Solution (Python):
import sys
import collections


def input():
    return sys.stdin.readline()[:-1]


def main():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    mod = 10**9+7
    ans = 0
    count = 0
    c = collections.Counter(A)
    k = list(c.keys())
    k.sort(reverse=True)

    
    s = c[k[0]]
    for i in k[1:]:
        count += s*c[i]
        s += c[i]

    for i, v in enumerate(A):
        for j in range(0, i):
            if A[j] > v:
                ans += 1
    

    print((ans*K+K*(K-1)//2*count) % mod)


if __name__ == '__main__':
    main()

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

Solution (Python):
def solve():
    mod = 10 ** 9 + 7
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    count = 0
    for i in range(N):
        inner_count = 0
        all_count = 0
        for j in range(N):
            if A[i] < A[j]:
                all_count += 1
            if i > j and A[i] < A[j]:
                inner_count += 1
        
        
        
        count += all_count * ((K - 1) * K // 2) + inner_count * K
        count %= mod
    print(count)


if __name__ == '__main__':
    solve()

Solution (Python):

MOD = 10 **9 +7
 
N, K = [int(v) for v in raw_input().split()]
A = [int(v) for v in raw_input().split()]

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





res = ((K + 1) * K)/2 * inversions + (K * (K-1))/2 * versions
res = res % MOD
print(res)

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

ans=0
L= (K*(K+1)//2) % 1000000007

for i in range(N):
    for j in range(N):
        if i==j:
            continue
        if A[i] > A[j]:
            if i < j:
                ans = (ans + L) % 1000000007
            else:
                ans = (ans + L-K) % 1000000007

print(int(ans))

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

c=0
for e,i in enumerate(A):
    for j in A[e:]:
        if i>j:c+=K*(K+1)//2
        if i<j:c+=K*(K-1)//2
            
print(c%(10**9+7))

Solution (Python):

from collections import Counter
MOD = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
li = [0] * (2001)
for i in range(n):
    for j in range(i + 1, n):
        if a[i] > a[j]:
            li[a[i]] += 1
ans = 0
dic = Counter(a)
num = 0
for i in sorted(dic.keys()):
    if i > 1:
        ans += dic[i] * (num * (k - 1) * k // 2) + li[i] * k
        ans %= MOD
    num += dic[i]
print(ans)

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

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

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

A_s = sorted(A)
num_out = 0
for i in range(0, N):
    for j in range(i+1, N):
        if A_s[i] < A_s[j]:
            num_out += 1

MOD = int( 1e9 + 7 )

print((K*(K-1)//2*num_out+K*num_in)%MOD)

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


Aset = set(As)
As_tmp = [a for a in As]
from collections import defaultdict
d = defaultdict(int)











cnt = 0
for i,ai in enumerate(As):
    for aj in As[i:]:
        
        if ai > aj:
            cnt += 1 

sumA = 0
rA = sorted(As,reverse=True)
for i,ai in enumerate(rA):
    for aj in rA[i:]:
        if ai > aj:
            sumA += 1 

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

Solution (Python):
import math
import sys
import numpy as np
from collections import defaultdict, deque, Counter 
from itertools import accumulate, product, permutations,combinations, combinations_with_replacement
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd

max_value = 1000000000
min_value = -1000000000
sys.setrecursionlimit(max_value)

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

big_num = 10**9 + 7
single = 0
double = 0
for i in range(len(a_list)):
    for j in range(len(a_list)):
        if i < j and  a_list[i] > a_list[j]:
            single += 1
        if a_list[i] > a_list[j]:
            double += 1


coeff = (k*(k+1)//2)%big_num
value = (coeff * single)%big_num

if k == 1:
    print(single)
    sys.exit()
else:
    value = k * single
    value += (k*(k-1)//2) * double
    value %= big_num
    print(value)

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

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

d={}
B=sorted(A)
for a in B:
	if a not in d:d[a]=1
	else:d[a]+=1

PP=10**9+7
y=0
t=0
for a in d:
	y+=(t*d[a])%PP
	t+=d[a]
print((((cnt*K)%PP+(y*(K*(K-1)//2))%PP))%PP)

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

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

MOD = 1000000007
result = base * K + (diff * K * (K - 1) // 2)
result %= MOD
print(result)

Solution (Python):
def modInverse(a,m):
    m0 = m 
    y = 0
    x = 1
  
    if (m == 1) : 
        return 0
  
    while (a > 1) : 
        q = a // m 
        t = m 
        m = a % m 
        a = t 
        t = y 
        y = x - q * y 
        x = t 
  
    if (x < 0) : 
        x = x + m0 
  
    return x 

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

    ans = ans*k
    ans = ans%mod

    dist = {}
    for i in arr:
        if i not in dist.keys():
            dist[i] = 1
        else:
            dist[i] += 1

    arr = []
    for i in dist.keys():
        arr.append((i,dist[i]))

    arr.sort(reverse = True)
    count = 0
    total = 0
    for i in arr:
        total += i[1]

    
    for i in arr:
        total -= i[1]
        count += total*i[1]

    count = count*k*(k-1)
    count = count%mod
    count = count*modInverse(2,mod)
    count = count%mod
    ans += count
    print(ans%mod)
    


main()

Solution (Python):
import numpy as np

n, k = np.array(input().split(" ")).astype(int)
a = np.array(input().split(" ")).astype(int)

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

num_all = (num_less%(10**9 + 7)) * ((k*(k+1)//2)%(10**9+7))
num_all += (num_more%(10**9 + 7)) * ((k*(k-1)//2)%(10**9+7))
print(num_all%(10**9 + 7))

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))

n,k = m()

a = l()

aaa = [0 for i in range(n)]
co = [0 for i in range(2002)]


for i in range(n-1,-1,-1):
    aaa[i] = co[a[i]]
    for j in range(a[i]+1,2000+2):
        co[j] += 1


su = 0

for i in range(n-1,-1,-1):
    su += k * aaa[i]
    su %= mod
    su += (((k)*(k-1))//2)*co[a[i]]
    su %= mod


print(su)

Solution (Python):
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * 2001
c = [0] * 2001
cnt = 0
for i in range(len(a)):
    b[a[i]] += 1
for i in range(len(a)):
    c[a[i]] += 1
    sb = sum(b[a[i] + 1:])
    sc = sum(c[a[i] + 1:])
    ss = (sc + (sc + sb * (k - 1))) * k // 2
    cnt += ss
    cnt %= (10 ** 9 + 7)
print(cnt)

Solution (Python):
import sys

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

def main():
    def inv(a):
        a_sort = sorted(list(set(a)))
        n = len(a_sort) + 1
        bit = [0] * n
        tento = 0
        for ai, ak in enumerate(a):
            wa = 0
            i = ii = a_sort.index(ak) + 1
            while i:
                wa += bit[i]
                i -= i & -i
            tento += ai - wa
            while ii < n:
                bit[ii] += 1
                ii += ii & -ii
        return tento

    md = 10 ** 9 + 7
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    if k <= 4:
        a = a * k
        print(inv(a))
        exit()
    t1 = inv(a)
    t2 = inv(a * 2)
    t3 = inv(a * 3)
    d1 = t2 - t1
    d2 = t3 - t2
    dd = d2 - d1
    print((t1 + d1 * (k - 1) + dd * (k - 2) * (k - 1) // 2) % md)

main()

Solution (Python):
from collections import defaultdict

mod = 10**9 + 7

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

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

num_dic = defaultdict(int)
num_smaller = [0 for x in range(2001)]

for num in a:
  num_dic[num] += 1
  for i in range(num + 1, 2001):
    num_smaller[i] += 1

cnt = 0



for key, v in num_dic.items():
  
  cnt += (num_smaller[key] * v * (k * (k-1)) // 2) % mod
  


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

Solution (Python):
import sys

M = int(1e9 + 7)
n, k = map(int, sys.stdin.readline().strip().split())
xs = list(map(int, sys.stdin.readline().strip().split()))
x = 0
y = 0
for i in range(n):
    for j in range(n):
        if i < j and xs[i] > xs[j]:
            x += 1
        if i < j and xs[i] < xs[j]:
            y += 1

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

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

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

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

Solution (Python):
import math

n,k=map(int,input().split())
a = [int(i) for i in input().split()]
dic={}
ans=0
for i in a:
    if i in dic:
        dic[i]+=1
    else:
        dic[i]=1

dic=sorted(dic.items() , key=lambda x:x[0], reverse=True)
check=0
for i in range(len(dic)-1):
    ans+=dic[i][1]*(((1+(k-1))*(k-1))//2)*(n-check-dic[i][1])
    check +=dic[i][1]

check=0
for i in range(n):
    for j in range(i+1,n):
        if a[i]>a[j]:
            check+=1
    
    
print((ans+check*k)%(10**9+7))

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

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

a = 0
b = 0

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

ans = a*K*(K+1)//2 + b*(K-1)*K//2
ans %= mod
print(ans)

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

b = [0 for _ in range(2001)]
in_range = 0


for i in A:
    in_range += sum(b[i+1:])
    b[i] += 1
    

compare_to_another = 0
for i in A:
    compare_to_another += sum(b[i+1:])


answer = ( (in_range * k) + (compare_to_another * (k*(k-1))//2) ) % (10**9 + 7)
print(answer)

Solution (Python):
from bisect import bisect
mod = 10**9+7
n,k = map(int,input().split())
*a,= map(int,input().split())
b = []
ans = 0
for j,x in enumerate(a):
	i = bisect(b,x)
	ans += (j-i)*k
	b.insert(i,x)
a.sort(reverse=True)
bef = a[-1]
j=0
for i,cur in enumerate(a):
	if cur==bef:
		ans += k*(k-1)*j//2
	else:
		ans += k*(k-1)*i//2
		j = i
		bef = cur
print(ans%mod)

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

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

mae=0
ato=0
ans=0
sum = (k*(k-1))//2
for i in range(n):
    mae, ato = 0, 0
    for j in range(n):
        if a[i]>a[j]:
            if i<j:
                ato+=1
            else:
                mae+=1
    ans += (sum)*(mae+ato) + (ato*k)
    ans%=mod

print(ans)

Solution (Python):
INFTY=10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
if K==1:
    tot = 0
    for i in range(1,N):
        for j in range(i):
            if A[j]>A[i]:
                tot += 1
else:
    B = [0 for _ in range(2*N)]
    A = A+A
    for i in range(1,2*N):
        cnt = 0
        for j in range(i):
            if A[j]>A[i]:
                cnt += 1
        B[i] = cnt
    tot = 0
    for i in range(N):
        a = B[i]
        d = B[i+N]-B[i]
        tot = (tot + (K*(a-d))%INFTY + ((d*(K+1)*K)//2)%INFTY)%INFTY
print(tot)

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

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

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

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

count += back * (1+k) * k // 2 + forward * k * (k-1) // 2
ans = count % mod
print(ans)

Solution (Python):
n,k = map(int,input().split())
lst = [int(i) for i in input().split()]
ss = 0
for i in range(0,len(lst)):
    b,a = 0,0
    for ii in range(0,i):
        if lst[ii] < lst[i]:
            b += 1
    for ii in range(i,len(lst)):
        if lst[i] > lst[ii]:
            a += 1
    n1 = k
    tna = a*n1
    ta = a
    aa = n1*(tna+ta)//2
    n2 = k-1
    tnb = b*n2
    tb = b
    bb = n2*(tnb+tb)//2
    ss += aa+bb
print(ss%(10**9+7))

Solution (Python):
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = 1000000007
t = 0
for i in range(n):
    for j in range(n-i-1):
        if a[i+j+1] < a[i]:
            t += 1
a.sort()
s = 0
for i in range(n):
    for j in range(n-i-1):
        if a[i+j+1] > a[i]:
            s += 1
key = ((k%mod)*((k-1)%mod)//2)%mod
ans = ((t*k)%mod+(s*key)%mod)%mod
print(ans)

Solution (Python):
n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
ookii=[0]*n
num=[0]*n
for i in range(n):
    for j in range(n):
        if a[i]<a[j] and i!=j:
            ookii[i]+=1
            if i>j:
                num[i]+=1
ans=0
for i in range(n):
    ans+=k*(2*num[i]+(k-1)*ookii[i])//2
    ans%=1000000007
print(ans)

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

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

A.sort()

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

print((K * (K - 1) // 2 * inversion2 + K * inversion) % MOD)

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

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

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

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

cnt = 0
cnt2 = 0
for i, a1 in enumerate(A):
    for j, a2 in enumerate(A):
        if a2 < a1:
            cnt += 1
            if j > i:
                cnt2 += 1

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

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

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

a=0
b=0
for i in range(n-1):
    for j in range(n-1-i):
        if alis[i]>alis[i+1+j]:
            a+=1
        elif alis[i]<alis[i+j+1]:
            b+=1

aa=(a*k*(k+1)//2)%(10**9+7)
bb=(b*k*(k-1)//2)%(10**9+7)

ans=(aa+bb)%(10**9+7)
print(int(ans))

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

 
print(ans)

Solution (Python):
import numpy as np
n, k = map(int, input().split())
M = 10**9 + 7

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

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

def calc_t(tk):
    tmp = a * tk
    t = [0] * n
    for i in range(n):
        ans = 0
        for j in range(i + 1, n * tk):
            if tmp[i] > tmp[j]:
                ans += 1
        t[i] = ans
    return np.array(t)

t1 = calc_t(1)
t2 = calc_t(2) - t1 * 2
print((int(sum(t1)) * s(k) + int(sum(t2)) * s(k - 1)) % M)