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):
INF = 1000000007

n, k = map(int, input().split())
a = list(map(int, input().split()))
sum1 = 0
sum2 = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue    
        if a[i]>a[j]:
            if i <j:
                sum1+=1
            else:
                sum2 +=1
ans = sum1+sum2
x = sum1*k
y = ans *((k*(k-1))//2)
print(int((x+y)%INF))

Solution (Python):



import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n, k = map(int, input().split())
    al = list(map(int, input().split()))
    down1 = 0
    for i in range(n-1):
        for j in range(i+1,n):
            if al[i] > al[j]:
                down1 += 1

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

    mod = 10**9 + 7
    print((down1 * k + down2 * k * (k - 1) // 2) % mod)


if __name__ == '__main__':
    main()

Solution (Python):


list1 = input().split()
list2 = input().split()
N = int(list1[0])
K = int(list1[1])
a = [int(i) for i in list2]

cnt_l = 0
cnt_r = 0
for j in range(len(a)):
    for i in range(j):
        if a[i] > a[j]:
            cnt_l = cnt_l + 1
    for i in range(j, len(a)):
        if a[i] > a[j]:
            cnt_r = cnt_r + 1

res = ((cnt_l * K * (K+1) // 2) + (cnt_r * (K-1) * K //2)) % (10**9 + 7)

print(int(res))

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

Solution (Python):
def main():
    def c(x,y):
        if x > y:
            return 1
        else:
            return 0
    n,k = map(int,input().split())
    x = 1000000007
    kk = int(k*(k-1)//2)%x
    a = list(map(int,input().split()))
    c1 = []
    c2 = []
    for i in range(n):
        l = [c(a[i],p) for p in a]
        c1.append(sum(l))
        c2.append(sum(l[i:]))
    ans = ((sum(c1)%x)*kk)%x+((sum(c2)%x)*k)%x
    print(ans%x)
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi, factorial
from copy import deepcopy




MOD = 10**9+7

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def main():
    N,K = map(int, input().split())
    aa = list(map(int, input().split()))
    ans = ModInt(0)

    
    tmp = 0
    for i in range(N):
        for j in range(i,N):
            if i == j:
                continue
            if aa[i]>aa[j]:
                tmp += 1
    ans += tmp * K

    
    tmp = 0
    for i in range(N):
        for j in range(N):
            if aa[i]>aa[j]:
                tmp += 1
    ans += tmp * (K*(K-1)//2)
    print(ans)

if __name__ == '__main__':
    main()

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

for i in range(n):
    for j in range(n):
        if i > j:
            if a[i] > a[j]:
                fflag += 1
        elif i < j:
            if a[i] > a[j]:
                bflag += 1

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

Solution (Python):
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N,K=map(int,input().split())
l=list(map(int,input().split()))

cnt=0
cnt2=0
p=10**9+7
for i in range(N):
	for j in range(N):
		if l[i]>l[j] and j>i:
			cnt+=1
for k in range(N):
	for m in range(N):
		if l[k]>l[m] and k>m:
			cnt2+=1
Cn=K*(K+1)//2*cnt+(K-1)*K//2*cnt2
print(Cn%p)

Solution (Python):
n,k = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
MOD = 10 ** 9 + 7
t = (k*(k-1))//2
ans = 0
cnt1,cnt2 = 0,0
for i in range(n):
    for j in range(i,n):
        if A[i]>A[j]:
            cnt1 += 1
cnt1 *= k

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

cnt2 *= t
print((cnt1+cnt2)%MOD)

Solution (Python):
import sys

stdin = sys.stdin

sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

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

def main():
  n, k = an()
  a = list(an())

  mod = int(1e9)+7
  ans = 0
  x = a[:] 
  for i, ai in enumerate(x):
    cnt = 0
    for j in range(i+1, n):
      if ai > x[j]:
        cnt += 1
    tcnt = 0
    for j in range(i+1):
      if ai > x[j]:
        tcnt += 1

    ans += f(k) * cnt
    ans %= mod
    ans += f(k - 1) * tcnt
    ans %= mod

  print(ans)

main()

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

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

bit = Bit(2020)
X = 0
for i, p in enumerate(A):
    bit.add(p, 1)
    X += i + 1 - bit.sum(p)

bit = Bit(2020)
Y = 0
for i, p in enumerate(A * 2):
    bit.add(p, 1)
    Y += i + 1 - bit.sum(p)
Y -= 2 * X

ans = (X * K + Y * K * (K - 1) // 2) % mod
print(ans)

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

import numpy as np

MOD = 10**9 + 7

N,K = map(int,input().split())
A = np.array(input().split(), dtype=np.int64)


def type_1():
    bl1 = A[:,None] > A[None,:]
    bl2 = np.arange(N,dtype=np.int64)[:,None] < np.arange(N,dtype=np.int64)[None,:]
    x = ((bl1 & bl2)*1).astype(np.int64).sum() % MOD
    return x*K%MOD

def type_2():
    
    counter = np.bincount(A)
    cum = counter.cumsum()
    larger = N-cum
    x = (larger * counter % MOD).sum() % MOD
    y = K*(K-1)//2 % MOD
    return x*y%MOD

answer = (type_1() + type_2()) % MOD
print(answer)

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

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

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

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

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

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

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

MOD = 10**9+7

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

from collections import Counter
ctr = Counter(A)

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

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

print(ans)

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

Solution (Python):
from sys import stdin
import numpy as np

n, k = map(int, stdin.readline().rstrip().split(' '))
arg = np.array(list(map(int, stdin.readline().rstrip().split(' '))))
small = []
for i, val in enumerate(arg):
    small.append([np.count_nonzero(arg[:i] < val), np.count_nonzero(arg[i+1:] < val)])
smallnd = np.array(small)

a, b = np.sum(smallnd, axis=0)

res = k*(int(a)*(k-1)+int(b)*(k+1))//2

print(int(res % (10**9+7)))

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

inversion = 0
for i in range(len(a_list)):
    for j in range(i + 1, len(a_list)):
        if a_list[i] > a_list[j]:
            inversion += 1

total_lower = 0
for i in range(len(a_list)):
    total_lower += len([x for x in a_list if x < a_list[i]])


total_k = (K * (K - 1)) // 2
total = (total_lower * total_k+ inversion * K) % MOD
print(total)

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

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

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

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    N, K = [int(i) for i in input().split()]
    a_list = [int(i) for i in input().split()]
    cnt = 0
    cnt = sum([a_list[i] > a_list[j] for i in range(N) for j in range(i, N)])
    second_cnt = sum([a_list[i] > a_list[j] for i in range(N) for j in range(i)])
    if K > 1:
        second_cnt *= (K * (K - 1)) // 2
    cnt = cnt * ((K * (K + 1)) // 2)
    print((cnt + second_cnt) % (10 ** 9 + 7))


if __name__ == "__main__":
    main()

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

inversion = 0
for i in range(len(a_list)):
    for j in range(len(a_list) - 1, i, -1):
        if a_list[j] < a_list[j - 1]:
            a_list[j], a_list[j - 1] = a_list[j - 1], a_list[j]
            inversion += 1

total_lower = 0
for i in range(len(a_list)):
    total_lower += len([x for x in a_list if x < a_list[i]])


total_k = (K * (K - 1)) // 2
total = (total_lower * total_k+ inversion * K) % MOD
print(total)

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

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

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

res = cnt*k + cnt_2*k*(k-1)//2
res %= 10**9 + 7
print(res)

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

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

d=10**9+7

c=0

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

cc=0

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

cc=cc%d

e=(K*(K-1)//2)%d

print(int(((c*K)%d+(cc*e)%d)%d))

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
a0 = a[0]
an = a[n-1]
now = a0
c_self = 0
c_inter = 0
for i in range(n):
    for j in range(i,n):
        
        
        if a[i] > a[j]:
            c_self += 1
        if a[i] != a[j]:
            c_inter += 1

t =( (k-1) * k//2) % (10**9 + 7)
l = (k * c_self) % (10**9 + 7)
q = (t * c_inter) % (10**9 + 7)

ans = (l + q ) % (10**9 + 7)
print(int(ans))

Solution (Python):

prime = 10**9+7

def sowa(num):
  return int((1+num)*num//2)

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

tento1 = [sum([1 if a[i]>a[j] else 0 for j in range(i+1,n)]) for i in range(n-1)]
tento2 = [sum([1 if a[i]>a[j] else 0 for j in range(n)]) for i in range(n)]


ret = (sum(tento1) *k %prime) + (sum(tento2) *(sowa(k-1) %prime) %prime)
print(int(ret%prime))

Solution (Python):


import math
import sys
import itertools

DIV_NUM = 1000000000 + 7

N,K = map(int, input().split())
A = [int(x) for x in input().split()]
if N==1:
    print(0)
    exit()

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

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

answer = answer % DIV_NUM
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Solution (Python):
MOD = 1000000007
N,K = map(int,input().split())
A = list(map(int,input().split()))
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt
def sigma(k):
    return int(k*(k+1)//2)
C = []
for k in range(2):
    C.extend(A)
cnt = bubble_sort(A)
diff = bubble_sort(C) - 2 * cnt
a = (K*cnt)
b = (diff*sigma(K-1))
print ((a+b)%MOD)

Solution (Python):
from bisect import bisect

def solve():
	mod = 10**9+7
	n,k,*a = map(int,open(0).read().split())
	b = []
	ans = 0
	for j,x in enumerate(a):
		i = bisect(b,x)
		ans += (j-i)*k
		b.insert(i,x)
	bef = max(a)
	j=0
	for i,cur in enumerate(b[::-1]):
		if cur==bef:
			pass
		else:
			j = i
			bef = cur
		ans += k*(k-1)*j//2
	print(ans%mod)

if __name__=="__main__":
	solve()

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

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

A=list(map(int,input().split()))
L=[0]*N
R=[0]*N

for i in range(N):
    for j in range(N):
        if j<i and A[j]<A[i]:
            L[i]+=1
        if j>i and A[j]<A[i]:
            R[i]+=1
ans = 0
K1=((1+K)*K//2)%(10**9+7)
K2=(K*(K-1)//2)%(10**9+7)

for i in range(N):
    ans +=(R[i]*K1+L[i]*K2)%(10**9+7)

ans =ans%(10**9+7)

print(int(ans))

Solution (Python):
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
cnt = 0
cnt2 = 0
for i, ai in enumerate(a):
    for j in range(i, n):
        if ai > a[j]:
            cnt += 1
    if i > 0:
        for j in range(i):
            if ai > a[j]:
                cnt2 += 1

if k % 2 == 0:
    mul = (1 + k) * (k // 2)
else:
    mul = (1 + k) * (k // 2) + (k // 2 + 1)
mul2 = 0
if k > 1:
    k -= 1
    if k % 2 == 0:
        mul2 = (1 + k) * (k // 2)
    else:
        mul2 = (1 + k) * (k // 2) + (k // 2 + 1)
print(((cnt * mul) + (cnt2 * mul2)) % 1000000007)

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

Solution (Python):
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
k_sum = (k-1)*k//2

ans = 0
minus = 0
for i in range(n):
    tentou1 = 0
    tentou2 = 0
    for j in range(n):
        if i<j and a[i]>a[j]:
            tentou1 += 1
        if a[i]>a[j]:
            tentou2 += 1
    ans += tentou1*k+tentou2*k_sum

print(ans%1000000007)

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

MOD=10**9+7

def count(A,N):
    arr=[0]*N
    for i, ai in enumerate(A[:-1]):
        cnt=0
        for aj in A[i+1:]:
            if ai > aj:
                cnt+=1
        arr[i]=cnt
    return arr

s1=sum(count(A,N))
s2=sum(count(sorted(A,reverse=True),N))
v=K*(K-1)//2
print((s1*K+v*s2)%MOD)

Solution (Python):
import copy



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


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

b = copy.deepcopy(a)

initial = bubble_sort(a)
ans = initial
bigger = [0] * n



for i in range(n):
    cnt = 0
    for j in b:
        if b[i] > j:
            cnt += 1
    bigger[i] = cnt

d = sum(bigger)

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

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

mod = 10**9 + 7
B, C = [0]*N, [0]*N
for i in range(N):
    ai = A[i]
    for j in range(i, N):
        aj = A[j]
        if ai > aj:
            B[i] += 1
    for j in range(i + 1):
        aj = A[j]
        if ai > aj:
            C[i] += 1

ans = (sum(B) * K * (K + 1) // 2) % mod
ans += (sum(C) * (K - 1) * K // 2) % mod
print(ans % mod)

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

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

    A=0
    B=0
    mina=min(a)
    for i in reversed(range(len(a))):
        if a[i]==mina:continue
        for j in range(i,len(a)):
            if a[j]<a[i]:
                A+=1
    for i in reversed(range(len(a))):
        if a[i]==mina:continue
        for j in range(len(a)):
            if a[j]<a[i]:
                B+=1
    ans=int(((2*A+(K-1)*B)*K//2)%(10**9+7))
    print('{}'.format(ans))

resolve()

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
X = 10**9+7
count_self=0
for i,a in enumerate(A):
    j=N-1
    while i<j:
        if a>A[j]:
            count_self+=1
        j-=1
num = [0]*2000
for a in A:
    num[a-1]+=1
count=0
a=0
for n in num:
    if n != 0:
        if a == 0:
            a=n
        else:
            count = count + n*a
            a+=n
print((count_self*K + count*K*(K-1)//2)%X)

Solution (Python):
import copy



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


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

b = copy.deepcopy(a)

initial = bubble_sort(a)
ans = initial
bigger = [0] * n



for i in range(n):
    cnt = 0
    for j in b:
        if b[i] > j:
            cnt += 1
    bigger[i] = cnt

d = sum(bigger)

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

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

Solution (Python):
INF = 1000000007

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

for i in range(len(a)):
    for j in range(len(a)):
        if i == j: continue
        
        if a[i] > a[j]:
            if i < j:
                ans_i += 1
            else:
                ans_e += 1
x = ans_i * k
ans = ans_i + ans_e
y = ans * ((k * (k-1) ) // 2)
print(int((x + y) % INF))

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


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

def sigma(k):
    
    return k*(k+1)//2








C = []
for k in range(2):
    C.extend(A)
cnt = bubble_sort(A)

diff = bubble_sort(C) - 2 * cnt

a = (K*cnt)
b = (diff*sigma(K-1))
print ((a+b)%MOD)

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

mod = 10**9 + 7
tota = 0
totd = 0

for i in range(N): 
    for j in range(i+1, N): 
        if A[i] > A[j]:
            tota += 1
    for k in range(N): 
        if A[i] > A[k]:
            totd += 1

ans = (tota * K + K*(K-1)//2 * totd) % mod 
print(int(ans))

Solution (Python):

N,K = map(int,input().split())
A = list(map(int,input().split()))
B = A*2
d = []

for i in range(N*2):
  num = B[i]
  target = B[i+1:]
  d.append(len([n for n in target if num > n]))
  
d_each = sum(d[:N]) - sum(d[N:])
first = sum(d[N:])
print(int((K * first + K * (K - 1) * d_each // 2) % (10 ** 9 + 7)))

Solution (Python):


import math
import sys
import itertools
import numpy as np

DIV_NUM = 1000000000 + 7

INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])

A = [int(x) for x in input().split()]
AA = np.array(A)
if N==1:
    print(0)
    exit()


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

answer = bubble_sort(AA)

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


answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

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

Solution (Python):
import bisect
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
 
n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
bit = Bit(2010 * 2)
ans = 0
 
for i, p in enumerate(a):
    bit.add(p, 1)
    ans += i + 1 - bit.sum(p)
 
a.sort()
big = 0
for item in a:
    big += n - bisect.bisect_right(a, item)
 
times = (k * (k - 1) // 2) % MOD
ans2 = (ans * k) % MOD + (big * times) % MOD
ans2 %= MOD
print(ans2)

Solution (Python):
import copy
import sys

input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = copy.deepcopy(a)

w = 10 ** 9 + 7

cnta = 0
cntb = 0
for i in range(len(a)):
    for j in range(len(a) - 1, i, -1):
        if a[j] < a[j - 1]:
            a[j], a[j - 1] = a[j - 1], a[j]

            cnta += 1

for i in range(len(b)):
    for j in range(len(b)):
        if b[i] > b[j]:
            cntb += 1

wa = (k * (k - 1) // 2) * cntb + cnta * k
print(wa % w)

Solution (Python):


from itertools import combinations
from collections import defaultdict
from pprint import pprint
import math
import datetime
import sys
import fcntl
import time


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

smaller = [0] * N
rightSmaller = [0] * N

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

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

ans = 0
for i in range(N):
    ans += smaller[i]*K*(K-1)//2 + rightSmaller[i]*K
    ans %= 10**9 + 7

print(ans)

Solution (Python):
import numpy as np
N,K = map(int,input().split())
Alist = np.array(list(map(int,input().split())))
counter = 0
for i,A in enumerate(Alist,0):
    fir_tenti = np.count_nonzero(A>Alist[i:])
    counter += (K*fir_tenti*(K+1))//2
    second_tenti = np.count_nonzero(A>Alist[:i+1])
    counter += (second_tenti*K**2-second_tenti*K)//2

print(int(counter%1000000007))

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

def cal(A, N):
    cnt1 = 0
    cnt2 = 0
    for i in range(N):
        for j in range(i+1,N):
            if A[N-1-j] > A[N-1-i]:
                cnt1 += 1
    for i in range(N):
        for j in range(N):
            if A[N-1-i] < A[j]:
                cnt2 += 1
    
    return int(cnt1), int(cnt2)
    
    
x, y = cal(A,N)
R = int(1*10**9 +7)
tmp = K*(K-1)//2
ans =  tmp*y + x*K
print(int(ans%R))

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


for i in range(n):
  for j in range(n):
    if i<j:
      if a[i]>a[j]:
        S1+=1
        S1%=(10**9+7)
        

for t in range(n):
  for T in range(n):
    if a[t]>a[T]:
      S2+=1
      S2%=(10**9+7)
      

l=len(list(set(a)))
if l==1:
  print(0)
  exit()


if k>=2:
  K=((k*(k-1))//2)%(10**9+7)
elif k==1:
  K=1


ans+=(S1*k)%(10**9+7)
ans+=(S2*K)%(10**9+7)


ans%=10**9+7


print(ans)

Solution (Python):
N,K = map(int, input().split())
A = list(map(int, input().split()))
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt
cnt_A = bubble_sort(A)
A_min=0
for i in range(len(A)):
  l_odd = [k for k in A if k<A[i]]
  A_min += len(l_odd)
result = int((cnt_A*K + A_min*(K-1)*K//2)%((10**9)+7))
print(result)

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):
import numpy as np

N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)

B = 0
C = 0

mod = 10**9 + 7

for i in range(N):
    D = A[i:]
    B = (B + np.sum(D < A[i])) % mod 
    C = (C + np.sum(A < A[i])) % mod 
    
k_sum = int((K-1) * K//2) % mod 

E = (B * K) % mod 
F = (C * k_sum) % mod 

print(int((E+F) % mod ))

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

x = 0
for l in range(N - 1):
  for r in range(l + 1, N):
    if A[l] > A[r]:
      x += 1

      
AA = A + A
y = 0
for l in range(2 * N - 1):
  for r in range(l + 1, 2 * N):
    if AA[l] > AA[r]:
      y += 1
y -= 2 * x

  
print(int((K * x + K * (K - 1) * y // 2) % (10 ** 9 + 7)))