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()))
MOD = 10 ** 9 + 7

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

ans = (cnt*k + y*k*(k-1)//2)%MOD
print(ans)

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

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

memo = [0]*N
tmp = [0]*(2002)
sm = [0]*(2002)

for i in range(N):
  for j in range(As[i]+1,2001):
    memo[i] += tmp[j]
  tmp[As[i]] += 1
  
for i in range(2000, 0, -1):
  sm[i] += sm[i+1] + tmp[i]
  
rlt = 0

for i in range(N):
  rlt += (K*(K-1)*sm[As[i]+1]//2 + K*memo[i]) % P
  rlt %= P
  
print(rlt)

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

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

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7
R=[0]*N
L=[0]*N
for i in range(N):
    r,l=0,0
    a=A[i]
    for j in range(N):
        if i<j:
            if a>A[j]:
                r+=1
        else:
            if a>A[j]:
                l+=1
    R[i]=r
    L[i]=l
ans=0
for i in range(N):
    ans+=K*R[i]+(L[i]+R[i])*(K-1)*K//2%mod
    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):
    c_0 = 0
    c_1 = 0
    for j in range(n):
        if i == j:
            pass
        elif a[i] > a[j]:
            if i < j:
                c_1 += 1
            else:
                c_0 += 1      
    ans += c_1*k*(k+1)//2 + c_0*k*(k-1)//2
    ans %= mod
print(ans)

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

count_inner = 0
for i in range(N):
    for j in range(i,N):
        if A[i] > A[j]:
            count_inner += 1
count_outer = 0
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            count_outer += 1
def fact(n):
    if n>1:
        return n*fact(n-1)%mod
    else:
        return 1

answer = (count_inner*K + count_outer*K*(K-1)//2)%mod

print(answer)

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

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

a.sort()
cnt2 = 0
c = 0
i = 0
c_n = a[0]
while True:
    cnt = 0
    while a[i + cnt] == c_n:
        cnt +=1
        if i + cnt == n:
            break
    cnt2 += cnt*c
    c += cnt
    i += cnt
    if i == n:
        break
    c_n = a[i]

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

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

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

a.sort()
cnt2 = 0
c = 0
i = 0
c_n = a[0]
while True:
    cnt = 0
    while a[i + cnt] == c_n:
        cnt +=1
        if i + cnt == n:
            break
    cnt2 += cnt*c
    c += cnt
    i += cnt
    if i == n:
        break
    c_n = a[i]

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

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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 power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


inf = 10 ** 18
mod = 10 ** 9 + 7

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

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
count=0
sm=[0 for i in range(n)]
sm2=[0 for i in range(n)]
for i in range(n):
    for j in range(n):
        if lis[i]>lis[j]:
            if i<j:
                sm2[i]+=1
            else:
                sm[i]+=1

ans=0
for i in range(n):
    ans=(ans+sm[i]*((k*(k-1))//2))%mod
    ans=ans+sm2[i]*((k*(k+1))//2)%mod
print(ans%mod)

Solution (Python):
import sys
from collections import defaultdict, deque, Counter
import math
 

from bisect import bisect_left, bisect_right

 

 

input = sys.stdin.readline
 
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]
 
INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
 
class Segtree_op():
     def __init__(self, n):
         self.size = 1
         while(n >= 1):
             self.size = self.size << 1
             n = n//2
 
         self.arr = [self.unit() for i in range(self.size*2)]
 
     def op(self, lch, rch):
         
         return lch + rch
 
     def unit(self):
         return 0
 
     def update(self, k, val):
         k += self.size - 1
         self.arr[k] = val
         while(k):
             k = (k - 1) // 2
             self.arr[k] = self.op(self.arr[k*2 + 1], self.arr[k*2 + 2])
 
     def query(self, l, r):
         L = l + self.size
         R = r + self.size
         s = self.unit()
         while L < R:
             if R & 1:
                 R -= 1
                 s = self.op(s, self.arr[R - 1])
 
             if L & 1:
                 s = self.op(s, self.arr[L - 1])
                 L += 1
             L >>= 1
             R >>= 1
         return s
 
 
     def show(self):
         idx = 1
         while(idx <= self.size):
             print(self.arr[idx - 1:idx * 2 - 1])
             idx *= 2
def tento(nums):
    st = Segtree_op(max(nums))
    ret = 0
    for i, num in enumerate(nums):
        st.update(num, st.query(num, num+1)+1)
        
        ret += i - st.query(0, num+1) + 1

    return ret



def main():
    n, kk = getList()
    nums = getList()
    ten = tento(nums)
    oneset = 0
    for k, v in Counter(nums).items():
        oneset += (n - v) * v
    
    print((kk * ten + kk * (kk-1) * oneset // 4)% MOD)

if __name__ == "__main__":
    main()

Solution (Python):
from typing import Optional, Sequence


class BinaryIndexedTree:
    """Binary Indexed Tree (Fenwick Tree): O(logN)

    References:
        http://hos.ac/slides/20140319_bit.pdf
    """

    __slots__ = ["_size", "_tree", "is_zero_origin"]

    def __init__(
        self,
        size: int,
        initial_values: Optional[Sequence[int]] = None,
        is_zero_origin: bool = True,
    ):
        self._size = size
        self._tree = [0] * (size + 1)
        self.is_zero_origin = is_zero_origin

        if initial_values:
            for i, a in enumerate(initial_values):
                self.add(i, a)

    def add(self, index: int, value: int) -> None:
        """Add value to tree[index], O(logN)."""
        if self.is_zero_origin:
            index += 1
        while index <= self._size:
            self._tree[index] += value
            index += index & -index

    def sum(self, index: int) -> int:
        """Return the sum of [1, index] in O(logN)."""
        ret = 0
        while index > 0:
            ret += self._tree[index]
            index -= index & -index
        return ret

    def range_sum(self, left: int, right: int) -> int:
        """Return the range sum of [left, right] in O(logN)."""
        if not self.is_zero_origin:
            left -= 1
        return self.sum(right) - self.sum(left)


def point_add_range_sum():
    
    N, Q, *X = map(int, open(0).read().split())
    A, queries = X[:N], X[N:]
    tree = BinaryIndexedTree(N, A)
    res = []
    for com, x, y in zip(*[iter(queries)] * 3):
        if com:
            res.append(tree.range_sum(x, y))
        else:
            tree.add(x, y)
    print("\n".join(map(str, res)))


def jsc2019_qual_b():
    
    N, K, *A = map(int, open(0).read().split())
    tree = BinaryIndexedTree(2000, is_zero_origin=False)
    x = 0
    for i, a in enumerate(A, 1):  
        tree.add(a, 1)
        x += i - tree.sum(a)
    y = -x
    for i, a in enumerate(A, 1):  
        tree.add(a, 1)
        y += i + N - tree.sum(a)
    MOD = 10 ** 9 + 7
    print((x * K + y * K * (K - 1) // 2) % MOD)


if __name__ == "__main__":
    
    jsc2019_qual_b()

Solution (Python):
N, K, *A = map(int, open(0).read().split())

cntr = [0]*N
cntl = [0]*N


for i, a in enumerate(A):
    l = r = 0
    for b in A[:i]:
        if a > b:
            l += 1
    for b in A[i+1:]:
        if a > b:
            r += 1
    cntr[i] = r
    cntl[i] = l+r

mod = 10**9 + 7
ans = 0
for r in cntr:
    x = r * K % mod
    ans = (ans + x) % mod

c2 = K*(K-1)//2
for l in cntl:
    x = l*c2%mod
    ans = (ans + x) % 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-1):
    for j in range(i+1,n):
        if a[i] > a[j]: cnt += 1

y = 0
for a1 in a:
    for a2 in a:
        if a1 > a2: y += 1

ans = (cnt * k + y * k * (k-1)//2)%MOD
print(ans)

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

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

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

from collections import Counter
ctr = Counter(A)
inv2 = 0
s = 0
for _,v in sorted(ctr.items()):
    inv2 += v * s
    s += v
ans += inv2 * K*(K-1)//2
ans %= MOD
print(ans)

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

ans = 0
mod = 10**9+7

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

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

if n == 1:
    print(0)
    exit()

ans = 0
for i in range(n-1):
    for j in range(i, n):
        if A[i] < A[j]:
            ans += (k-1)*k//2
        elif A[i] > A[j]:
            ans += k*(k+1)//2
        else:
            pass
        ans %= mod
print(ans)

Solution (Python):
def solve():
  ans = 0
  mod = 10**9+7
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  for i in range(N):
    for j in range(i+1,N):
      if A[i]>A[j]:
        ans += 1
  ans *= K
  A.sort()
  lis = [0]*N
  for i in range(1,N):
    if A[i]>A[i-1]:
      lis[i] = i
    else:
      lis[i] = lis[i-1]
  ans += sum(lis)*K*(K-1)//2
  ans %= mod
  return ans
print(solve())

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

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

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


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

back = [0]*n
for i in range(n):
    for j in range(i+1,n):
        if A[-(j+1)] < A[-(i+1)]:
            back[-(i+1)] += 1





wa = k*(k+1)//2

ans = (wa%mod)*sum(tentou)%mod

ans += sum(back)*(k-1)*k//2

print(ans%mod)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)
import math





class segtree:
    def __init__(self, n, init_val = 0):
        self.n = n
        self.init_val = init_val
        self.init = 0
        self.k = math.ceil(math.log2(n))
        if type(self.init_val) == int:
            self.bins = [init_val] * (1 << (self.k+1))
        elif len(self.init_val) >0:
            self.bins = [self.init] * (1<<(self.k+1))
            for idx, i in enumerate(range(1<<self.k, 1<<(self.k+1))):
                if len(self.init_val)>idx:
                    self.bins[i] = init_val[idx]
                else:
                    self.bins[i] = 0
        else:
            raise ValueError('init_val is invalid.')
        self.caliculate()

    def compare(self, l, r):
        return l + r

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        
        while True:
            
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        
        return ret

    def value(self, ind):
        return self.bins[(1<<self.k) + ind]

def run():
    N, K = list(map(int, sysread().split()))
    A = list(map(int, sysread().split()))
    st = segtree(2001, 0)
    T1 = [0] * N
    for i in list(range(N))[::-1]:
        T1[i] = st.eval(0, A[i]-1)
        st.update(A[i], st.value(A[i]) + 1)
        
    T2 = []
    for a in A:
        T2.append(st.eval(0, a-1))
    ret = 0
    mod = 10 ** 9 +7
    
    tmp_k2 = K * (K-1) // 2
    tmp_k2 %= mod
    for t1, t2 in zip(T1, T2):
        ret += K * t1 % mod
        tmp = tmp_k2
        tmp %= mod
        tmp *= t2
        tmp %= mod
        ret += tmp
        ret %= mod
    print(ret)

if __name__ == "__main__":
    run()

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
cnt = 0
for _ in range(n):
    for i in range(n-1):
        if A[i] > A[i+1]:
            A[i], A[i+1] = A[i+1], A[i]
            cnt += 1
AA = A*2
nn = len(AA)
out_cnt = 0
for _ in range(nn):
    for i in range(nn-1):
        if AA[i] > AA[i+1]:
            AA[i], AA[i+1] = AA[i+1], AA[i]
            out_cnt += 1
ans = (k*cnt % MOD + out_cnt * (k*(k-1)//2) % MOD) % MOD
print(ans)

Solution (Python):

n, k, *a = map(int, open(0).read().split())
m = 10**9 + 7
c = [0] * 2001
t1 = [0] * n
for i in range(n):
    c[a[i]] += 1
    t1[i] = sum(c[a[i] + 1:])
t2 = [0] * n
for i in range(n):
    c[a[i]] += 1
    t2[i] = sum(c[a[i] + 1:])
s1 = sum(t1)
s2 = sum(t2)
print((s1 * k % m + k * (k - 1) // 2 * (s2 - s1) % m) % m)

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

n, k = map(int, input().split())
alst = list(map(int, input().split()))
ans = 0
loop1 = k * (k - 1) // 2
loop2 = (k + 1) * k // 2
loop1 %= MOD
loop2 %= MOD

for i, num in enumerate(alst):
    for j, num2 in enumerate(alst):
        if num > num2:
            if i < j:
                ans += loop2
                ans %= MOD
            else:
                ans += loop1
                ans %= MOD
print(ans)

Solution (Python):
from collections import Counter

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
A_sort0 = sorted(A)
A_sort = sorted(list(set(A)))
counter = Counter(A)
ans = 0
for i in range(len(A_sort)):
    if i == 0:
        continue
    else:
        q = A_sort0.index(A_sort[i])
        ans += (q * (K * (K-1) // 2) * counter[A_sort[i]])  % MOD
        index = A.index(A_sort[i])
        cnt = 0
        p = 0
        for j in range(index, N):
            if A_sort[i] > A[j]:
                cnt += 1 * p
            elif A_sort[i] == A[j]:
                p += 1
        ans = (ans + (cnt * K)) % MOD
print(ans)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = pow(10,9)+7
ans_p1 = 0
for i in range(n):
    ans_p1 += sum([bool(A[i]>A[j]) for j in range(i+1,n)])

ans_p2 = 0
for i in range(n):
    ans_p2 += sum([bool(A[i]>A[j]) for j in range(n)])
print((ans_p1*k+ans_p2*k*(k-1)//2)%mod)

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

f=[0 for _ in range(n)]
s=[0 for _ in range(n)]
for i in range(n):
  for j in range(n):
    if a[i]>a[j]:
      s[i]+=1
  for j in range(i,n):
    if a[i]>a[j]:
      f[i]+=1
sm=0
for i in range(n):
  sm=(sm+k*f[i]+k*(k-1)//2*s[i])%(10**9+7)
print(sm)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
M = 10**9+7
from collections import defaultdict

d = defaultdict(int)

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

            if i < j:
                lcl_cnt += 1

ans = lcl_cnt * K

for _, v in d.items():
    ans += (K-1)*v*K//2%M
    
print(ans%M)

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

mod = 10**9 + 7


already = 0
for i in range(N):
    for j in range(i + 1, N):
        if (i == j):
            continue
        if (A[i] > A[j] and i < j):
            already += 1
already_count = already * K

L = []
L.extend(A)
L.extend(A)
count = 0
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        if (i == j):
            continue
        if (L[i] > L[j] and i < j):
            count += 1
inc = count - (already * 2)

tousa_sum = ((K - 1) * (1 + (K - 1))) // 2
print((inc * tousa_sum + already_count) % mod)

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

def main(n,k,a):
    MOD=10**9+7

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

    return x

if __name__=='__main__':
    n,k,a=readinput()
    ans=main(n,k,a)
    print(ans)

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

Solution (Python):

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

Solution (Python):
mod=10**9+7
n,k=map(int,input().split())
k1=(k*(k+1)//2)%mod
k2=(k*(k-1)//2)%mod
a=list(map(int,input().split()))
p=0
for i,j in enumerate(a):
    e=0
    for m in a[i:]:
        e+=j>m
    p=(p+(e*k1)%mod)%mod
for i,j in enumerate(a):
    e=0
    for m in a[:i]:
        e+=j>m
    p=(p+(e*k2)%mod)%mod
print(p)

Solution (Python):
n,k = map(int,input().split())
A=[int(i) for i in input().split()]
MOD = 10**9 + 7

def tent(a):
    t = len(a)
    res = 0
    for i in range(t-1):
        for j in range(i+1,t):
            if(a[i]>a[j]):
                res+=1
    return res
t1 = tent(A)
t2 = tent(A+A)-2*t1
ans = (t1*k%MOD + t2*(k*(k-1))//2%MOD)%MOD
print(ans)

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

MOD = 10**9 + 7


B = [0] * N

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



C = [0] * N

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


D = []
for i in range(N):
    tmp = B[i] * K + C[i] * K * (K-1) // 2 
    D.append(tmp % MOD)
print(sum(D)% MOD)

Solution (Python):
def m():
    MOD = 10 ** 9 + 7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    if len(A) == 1:
        return 0
    l2r = 0
    for i in range(N):
        prev = A[i]
        for j in range(i, N):
            if prev > A[j]:
                l2r += 1
    r2l = 0
    for i in range(N - 1, -1, -1):
        prev = A[i]
        for j in range(i, -1, -1):
            if prev > A[j]:
                r2l += 1

    ans1 = K * (K + 1) // 2 * l2r % MOD
    ans2 = (K - 1) * K // 2 * r2l % MOD
    return (ans1 + ans2) % MOD


print(m())

Solution (Python):
n,k,*a = map(int,open(0).read().split())
mod = 10**9+7
t1 = 0
for i in range(n-1):
  for j in range(i+1,n):
    if a[i]>a[j]:
      t1+=1
t2 = 0
c = 0
for i in sorted(list(set(a))):
  dc = a.count(i)
  t2 += c*dc
  c += dc
print((t1*k+t2*k*(k-1)//2)%mod)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
def tentou(lis):
    res = 0
    for i in range(len(lis)-1):
        for j in range(i+1, len(lis)):
            if lis[i] > lis[j]:
                res += 1
    return res
x = tentou(a)
y = tentou(a+a) - 2*x
print((x*k%mod + y*k*(k-1)//2 %mod)%mod)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=1000_000_000+7
l=[0]*n
r=[0]*n
total=[0]*n
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            if i>=j:
                l[i]+=1
            else:
                r[i]+=1
            total[i]+=1


ans=0

for i in range(n):
    ans+=(total[i]*k*(k+1))//2 
    ans-=k*l[i]

print(ans%mod)

Solution (Python):
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
b = [sorted(a).index(a[i]) for i in range(n)]
p = [b[i] * (k*(k+1)//2)for i in range(n)]
q = [0] * n
for i in range(n):
    num = 0
    for j in range(i,n):
        if a[j] > a[i]:
            num += 1
    q[i] = num
ans = sum(p)-sum(q)*k
print(ans%1000000007)

Solution (Python):

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

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

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

    def range_sum(self, l, r):  
        return self.sum(r) - self.sum(l - 1)


def main():
    N, K, *A = map(int, open(0).read().split())
    tree = BIT(2000)
    x = 0
    for i, a in enumerate(A, 1):  
        tree.add(a, 1)
        x += i - tree.sum(a)
    y = -x
    for i, a in enumerate(A, 1):  
        tree.add(a, 1)
        y += i + N - tree.sum(a)
    MOD = 10 ** 9 + 7
    print((x * K + y * K * (K - 1) // 2) % MOD)


if __name__ == "__main__":
    main()

Solution (Python):

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

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

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

    def range_sum(self, l, r):  
        return self.sum(r) - self.sum(l - 1)


def main():
    N, K = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    bit = BIT(2000)
    x = 0
    for i, a in enumerate(A, 1):  
        bit.add(a, 1)
        x += i - bit.sum(a)
    y = -x
    for i, a in enumerate(A, 1):  
        bit.add(a, 1)
        y += i + N - bit.sum(a)
    ans = (x * K + y * K * (K - 1) // 2) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from typing import Optional, Sequence


class BinaryIndexedTree:
    """Binary Indexed Tree (Fenwick Tree)
    Each operation runs in O(logN).

    References:
        http://hos.ac/slides/20140319_bit.pdf
    """

    __slots__ = ["_size", "_tree", "is_zero_origin"]

    def __init__(
        self,
        size: int,
        initial_values: Optional[Sequence[int]] = None,
        is_zero_origin: bool = True,
    ):
        self._size = size
        self._tree = [0] * (size + 1)
        self.is_zero_origin = is_zero_origin
        if initial_values:
            self._build(initial_values)

    def _build(self, initial_values: Sequence[int]):
        for i, a in enumerate(initial_values):
            self.add(i, a)

    def add(self, index: int, value: int) -> None:
        """Add value to tree[index], O(logN)."""
        if self.is_zero_origin:
            index += 1
        while index <= self._size:
            self._tree[index] += value
            index += index & -index

    def sum(self, index: int) -> int:
        """Return the sum of [1, index] in O(logN)."""
        ret = 0
        while index > 0:
            ret += self._tree[index]
            index -= index & -index
        return ret

    def range_sum(self, left: int, right: int) -> int:
        """Return the range sum of [left, right] in O(logN)."""
        if not self.is_zero_origin:
            left -= 1
        return self.sum(right) - self.sum(left)


def main():
    N, K, *A = map(int, open(0).read().split())
    tree = BinaryIndexedTree(2000, is_zero_origin=False)
    x = 0
    for i, a in enumerate(A, 1):  
        tree.add(a, 1)
        x += i - tree.sum(a)
    y = -x
    for i, a in enumerate(A, 1):  
        tree.add(a, 1)
        y += i + N - tree.sum(a)
    MOD = 10 ** 9 + 7
    print((x * K + y * K * (K - 1) // 2) % MOD)


if __name__ == "__main__":
    main()

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)%mod
y = (inner*k)%mod
print(int((x+y)%mod))