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
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


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())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


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

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



n, k = map(int, input().split())
a = list(map(int, input().split()))
inner = 0
for i in range(n - 1):
    cnt = 0
    for j in range(i + 1, n):
        if a[i] > a[j]:
            cnt += 1
    inner += cnt
inner *= k
outer = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if a[i] > a[j]:
            outer += 1
outer *= k * (k - 1) // 2
ans = (inner + outer) % MOD
print(ans)

Solution (Python):
n,k=map(int,input().split())
mod=10**9+7
a=list(map(int,input().split()))
tcount=0
hidaricount=[]
allcount=[]

for i in range(n):
    count=0
    for j in range(n):
        
        if a[i]<a[j]:
            count+=1
    allcount.append(count)


for i in range(n):
    count=0
    for j in range(i+1,n):
        
        if a[i]<a[j]:
            count+=1
    hidaricount.append(count)  



alls=sum(allcount)
hidari=alls-sum(hidaricount)

print((hidari*k + alls*k*(k-1)//2 )%mod)

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

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

ans = 0
if K % 2 == 0:
    k = ((K//2)*(K+1)) % MOD
else:
    k = (K*((K+1)//2)) % MOD
for i in range(N):
    ans = (ans + (((k * p[i]) % MOD - (K*q[i]) % MOD) % MOD)) % MOD
print(ans)

Solution (Python):
import sys
rs = lambda: sys.stdin.readline().strip()
ri = lambda: int(rs())
rs_ = lambda: [_ for _ in rs().split()]
ri_ = lambda: [int(_) for _ in rs().split()]

MOD = 10 ** 9 + 7

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

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

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

memo = [0] * (max_a + 1)
num = 0
for a in A:
    memo[a] += 1
    num += sum(memo[a+1:])

num_larger = 0
for a in A:
    num_larger += sum(memo[a+1:])

ans = ((num*K % MOD) + ((K*(K-1)//2)*num_larger) % MOD) % MOD
print(ans)

Solution (Python):
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] += x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]
    
    def query(self, i, j):
        
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j 
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: 
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: 
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result
    
    @property
    def data(self):
        return self.seg_data[self.N-1:self.N-1+self.n]


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

st = SegmentTree([0]*(max_a + 1))

num = 0
for a in A:
    st.update(a, 1)
    if a == max_a:
        continue
    num += st.query(a+1, max_a+1)

num_larger = 0
for a in A:
    if a == max_a:
        continue
    num_larger += st.query(a+1, max_a+1)

ans = ((num*K % MOD) + ((K*(K-1)//2)*num_larger) % MOD) % MOD
print(ans)

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

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

mod=10**9+7

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

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

print((inside*K+outside*(K-1)*K//2)%mod)

Solution (Python):
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

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

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

def inv(X):
    B = Bit(2000+1)
    inv = 0
    for i in range(len(X)):
        inv += i - B.sum(X[i])
        B.add(X[i], 1)
    return inv

A_inv = inv(A) % MOD
A2_inv = inv(A*2) % MOD

print((K*A_inv + ((K*(K-1))//2) * (A2_inv - 2*A_inv)) % MOD)

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

part=0
all=0
for i in range(n):
    for j in range(i,n):
        if a[i]>a[j]:
            part+=1
    for l in range(n):
        if a[i]>a[l]:
            all+=1

ans=(k*part)%MOD+(all*(k*(k-1))//2)%MOD
print(ans%MOD)

Solution (Python):
from collections import defaultdict
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=pow(10,9)+7
a0=0
d=defaultdict(lambda:0)
for i in range(n):
    a0+=len([s for s in a[:i] if s>a[i]])
    d[a[i]]+=1
keys=sorted(d.keys())
matagi=0
ni=n
for ky in keys:
    c=d[ky]
    ni-=c
    matagi+=ni*c
ans=(k*a0)%mod
ans+=(matagi*(k*(k-1))//2)%mod
print(ans%mod)

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

nums = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

ans = 0
for i in range(n):
    c = 0
    for j in range(i + 1, n):
        if nums[i] > nums[j]:
            c += 1
    ans += (c * k) % mod

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

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

gen=10**9+7

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

kaburi = 0
sorta=sorted(a)
scnt=0
for i in range(n-1):
  if sorta[i]==sorta[i+1]:
    scnt+=1
  if sorta[i]!=sorta[i+1]:
    kaburi+=scnt*(scnt+1)//2
    scnt=0
kaburi+=scnt*(scnt+1)//2

print((k*count+(n*(n-1)//2-kaburi)*k*(k-1)//2)%gen)

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

for i in range(N):
    for j in range(i + 1, 2 * N):
        if j == N:
            c = b
        if A[i] > A[j] and j < N:
            b += 1
        elif A[i] > A[j] and j >= N:
            c += 1
    
    if b == c - b:
        ans += b * K * (K + 1) // 2
    else:
        ans += b * K + (c - b) * K * (K - 1) // 2
    
    b = 0
    c = 0

print(ans % mod)

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

for i in range(N):
    for j in range(i + 1, 2 * N):
        if j == N:
            c = b
        if A[i] > A[j] and j < N:
            b += 1
        elif A[i] > A[j] and j >= N:
            c += 1
    if b == c - b:
        ans += b * K * (K + 1) // 2
    else:
        ans += b * K + (c - b) * K * (K - 1) // 2
    b = 0
    c = 0

print(ans % mod)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=1000000007
l1=0
l2=0
for i in range(n):
  for j in range(n):
    
    if i!=j:
      
      if a[i]>a[j]:
        l1+=1
        
        if i<j:
          l2+=1

k=k%mod
print((l2*k+l1*k*(k-1)//2)%mod)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  







N, K = read_ints()
A = read_ints()

n_origin = 0  
for a, b in combinations(A, r=2):
    if a > b:
        n_origin += 1

n_append = 0  


for a, b in combinations(A + A, r=2):
    if a > b:
        n_append += 1
n_append -= n_origin * 2
print((n_origin * K + n_append * (K - 1) * K // 2) % MOD)

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, k = na()
a = na()

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

print(ans % mod)

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

Solution (Python):
import math
n,k = map(int,input().split())
a = list(map(int,input().split()))
lim = int((1e+9)+7)
right = [0 for _ in range(n)]
left = [0 for _ in range(n)]
for i in range(n):
    for j in range(n):
        if a[j] < a[i]:
            if i < j:
                right[i] += 1
            else:
                left[i] += 1
ans = 0
def c(g):
    re = g*(g-1)//2
    return re

for i in range(n):
    ans = (ans - (left[i]*k) + ((right[i]+left[i])*c(k+1)))%lim
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter,defaultdict
mod=10**9+7
def main():
    n,k=map(int,input().split())
    A=[int(_) for _ in input().split()]
    ac=Counter(A)
    aci=list(ac.items())
    aci.sort(reverse=True)
    nn=len(aci)
    aciv_cum=[0]*nn
    m2=defaultdict(int)
    for i in range(1,nn):
        aciv_cum[i]=aciv_cum[i-1]+aci[i-1][1]
        m2[aci[i][0]]+=aciv_cum[i]
    ans=0
    for i,a in enumerate(A):
        b=m2[a]
        x=0
        for j in range(i):
            if A[j]>a:
                x+=1
        ans+=k*(2*x+(k-1)*b)//2%mod
    print(ans%mod)

if __name__=='__main__':
    main()

Solution (Python):
n,  k = list(map(int, input().split()))
al = list(map(int, input().split()))
cnt = [0]*n*2
dif = [0]*n
MOD = 10**9+7

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

for i in range(n):
    dif[i] = cnt[i] - cnt[i+n]
print((sum(cnt[n:])*k + sum(dif)*(1+k-1)*(k-1)//2) % MOD)

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    ans = 0
    mod = 10 ** 9 + 7
    for i in range(N):
        left = 0
        for j in range(i):
            if A[j] < A[i]:
                left += 1
        right = 0
        for j in range(i+1, N):
            if A[j] < A[i]:
                right += 1
        ans += (right * K * (K+1) + left * (K-1) * K) // 2
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import collections
N,K = map(int,input().split())
A = list(map(int, input().split()))
Ni_block = 0
Ni_inter = 0
bignum = pow(10,9)+7
for i in range(N):
   for j in range(N):
      if A[i]>A[j]:
         Ni_inter += 1
         if j>i:
            Ni_block+=1







   




Ni = Ni_block*K+(((K*(K-1))//2) % bignum)*Ni_inter
print(Ni%bignum)

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


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):  
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):  
        while i <= self.size:
            self.tree[i] += x
            i += i & -i  
    def pos(self, idx):  
        return self.sum(idx) - self.sum(idx-1)
    def lower_bound(self, w):  
        if w <= 0:
            return 0
        idx = 0
        k = 1
        while k*2 <= self.size:
            k *= 2
        while k > 0:
            if idx+k <= self.size and self.tree[idx+k] < w:
                w -= self.tree[idx+k]
                idx += k
            k //= 2
        return idx+1

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

bit = Bit(max(N, max(A)))
inv = 0
for i, a in enumerate(A):
	inv += i-bit.sum(a)
	bit.add(a, 1)
ans = inv*K%mod

cnt = [0]*(max(A)+1)
for a in A:
	for b in A:
		if a < b:
			cnt[a] += 1

for n in cnt:
	ans += n*((K*(K-1))//2)
	ans %= mod
print(ans)

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

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

ans = (trip * K) % mod
for n in num:
    ans += n * K * (K - 1) // 2
    ans %= mod
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    res = 0
    for i in range(n):

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

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

        res += x * k
        res %= mod
        res += y * (k - 1) * k // 2
        res %= mod

    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 12
import sys
sys.setrecursionlimit(1000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
import numpy as np

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    
    cnt = [0] * 2002
    ret = [0] * n
    for i in range(n):
        for j in range(a[i] + 1):
            cnt[j] += 1

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

if __name__ =='__main__':
    main()

Solution (Python):

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

a_out = [sum(bb > aa for bb in a ) for aa in a]
a_in = [sum(a[i] > a[j] for i in range(n) if i<j) for j in range(n)]

print( (sum(a_out)*k*(k-1)//2 + sum(a_in)*k)%mod )

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

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

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

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

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

ans=0


n,k=LI()
a=LI()
m=[0]*n
s=0
for i in range(n):
    for j in range(n):
        if a[i]<a[j]:
            m[j]+=1
        if a[i]<a[j] and i>j:
            s+=1
ans=s*k%mo
for i in range(n):
    ans+=m[i]*(k-1)*k//2
    ans%=mo
print(ans)

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

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

a_l += a_l
count2 = 0
for i in range(n*2):
    for j in range(i+1,n*2):
        if a_l[i] > a_l[j]:
            count2 += 1
count2 -= count1*2

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

print (ans)

Solution (Python):
import bisect


if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    
    
    B = A.copy()
    B.sort()
    cnt = [0 for _ in range(N)]
    for i, a in enumerate(A):
        idx = bisect.bisect_left(B, a)
        cnt[i] = idx

    ans = 0
    MOD = 1000000007
    for c in cnt:
        ans += c * (K - 1) * K // 2
        ans %= MOD

    
    
    B = A.copy()
    B = B[::-1]
    cnt = [0 for _ in range(N)]
    array = []
    for i, b in enumerate(B):
        idx = bisect.bisect_left(array, b)
        cnt[i] = idx
        bisect.insort_left(array, b)
    cnt = cnt[::-1]

    for c in cnt:
        ans += c * K
        ans %= MOD

    print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from collections import Counter
def solve():
    mod = 10**9+7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = [A[0]]
    fall_in = 0
    for i in range(1,N):
        fall_in += i - bisect_right(B,A[i])
        insort(B,A[i])
    c = Counter(A)
    double = 0
    for v in c.values():
        double += v*(v-1)//2
    fall_out = N*(N-1)//2 - double
    ans = fall_in * K % mod + fall_out * K*(K-1)//2 % mod
    ans %= mod
    return ans
print(solve())

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

MOD_BY = 7 + 10**9
ans = 0

for i in range(N):
    for j in range(N):
        Bi = A_list[i]
        Bj = A_list[j]
        
        if Bi > Bj:
            if K > 1:
                if i < j:
                    ans += (K+1)*K//2
                else:
                    ans += K*(K-1)//2
            else:
                if i > j:
                    ans += 1
                    
        ans %= MOD_BY
        
print(ans)

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

MOD_BY = 7 + 10**9
ans = 0

for i in range(N):
    for j in range(N):
        Bi = A_list[i]
        Bj = A_list[j]
        
        if Bi > Bj:
            if K > 1:
                if i < j:
                    ans += (K+1)*K//2
                else:
                    ans += K*(K-1)//2
            else:
                if i > j:
                    ans += 1
                    
        ans %= MOD_BY
        
print(ans)

Solution (Python):
import itertools

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



ans = 0
meets = [0] * N
for i in range(N):
    for j in range(N):
        ans += int(i < j and A[i] > A[j])
        meets[i] += int(A[i] > A[j])
ans *= K


ans += sum(meets) * K * (K - 1) // 2

print(ans % MOD)

Solution (Python):

import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') 
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(sys.stdin.readline()) 
def ifn(): return float(sys.stdin.readline()) 
def isn(): return sys.stdin.readline().split() 
def imn(): return map(int, sys.stdin.readline().split()) 
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) 
def fmn(): return map(float, sys.stdin.readline().split()) 
def iln(): return list(map(int, sys.stdin.readline().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, sys.stdin.readline().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N, K = imn()
A = iln()

la = len(A)
cnt = 0


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


cnt2 = 0
for i in range(la):
    for j in range(la):
        if A[i] > A[j]:
            cnt2 += 1
ans = cnt1*K
ans += cnt2*(K-1)*K//2
    
print(ans%MOD)

Solution (Python):
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
h = [0 for _ in range(2001)]
ans_1 = []
mi = 2001
for ai in reversed(a):
    h[ai] += 1
    mi = min(mi, ai)
    if mi == ai: continue
    ans_1.append(sum(h[:ai]))
h = [0 for _ in range(2001)]
ans_2 = []
mi = 2001
for ai in a:
    h[ai] += 1
    mi = min(mi, ai)
    if mi == ai: continue
    ans_2.append(sum(h[:ai]))
print(int((sum(ans_1) * (k * (k+1) // 2)) +
          (sum(ans_2) * (k * (k-1) // 2))) % mod)

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