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.



Sample input:
2 2
2 1


Sample output:
3

Submission status: Runtime Error

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


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

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

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

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

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

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

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


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

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

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

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

Submission status: Runtime Error

Solution code:
tmp = [int(i) for i in input().split(" ")]
n = tmp[0]
k = tmp[1]
a = [int(i) for i in input().split(" ")]
import numpy as np
uni, co = np.unique(a, return_counts=True)
ind = [np.sum(co[:uni.tolist().index(i)]) for i in a]
c = 0
a = np.array(a)
for i in range(len(a)):
    c += np.sum(a[i:]<a[i])
m = 10**9+7
tm = int(c)*int(k) % m
if k % 2 == 0:
    t = k * (k//2-1) + k//2
    t %= m
else:
    t = k * (k//2)
    t %= m
print((np.sum(ind)*t+tm) % m)

Submission status: Runtime Error

Solution code:
def b_sort(A):
    count=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]
                count+=1
    return count
N,K=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(K):
    b.extend(a)
print((int(b_sort(b))%1000000007)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = map(int, input().split())
A = A**K
c = 0
for a1 in A:
  for a2 in A:
    if a1>a2: c+=1
c = c/2%(10**9+7)
print(c)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
l1=l*k
# print(l1)
c=0
for i in range(n*k-1):
    
    for j in range(i+1,(n*k)):
        if l1[i]>l1[j]:
            c+=1
print(c%((10**9)+7))

Submission status: Runtime Error

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


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

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

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

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

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

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

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


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

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split()
a = list(map(int, input().split()))
s = [sum([b > c for c in a])*K for b in a]
p = [sum([l < a[i] for l in a[:i]]) for i in range(1, len(a))]
print(int((sum(s)-sum(p))%(1e9+7)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
DIV_NUM = 1000000007


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

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

tree = [0] * (N+1)

# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x&(-x)
def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x&(-x)
    return s

answer = N*(N-1)//2
for x in A:
    answer -= BIT_sum(tree,x)
    BIT_update(tree,x)

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 = (K * answer) + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
[N,K]=list(map(int,input().split()))
As=list(map(int,input().split()))
B=As*K

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

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

Submission status: Runtime Error

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


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

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

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

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

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

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

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


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

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

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

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

Submission status: Runtime Error

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*-~n

    def sum(self, i):
        s = 0
        while i:
            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()))

bit = Bit(n)
cnt = 0
for i, t in enumerate(a):
    bit.add(t, 1)
    cnt += i+1-bit.sum(t)
    cnt = cnt % (10 ** 9 + 7)


print(cnt * sum(range(1, k+1)) % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
[N,K]=list(map(int,input().split()))
As=list(map(int,input().split()))

count=0
for i in range(K*N-1):
    for j in range(i,N*K):
        if As[i]>As[j]:
            #print("{} {}".format(i,j))
            count+=1

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

Submission status: Runtime Error

Solution code:
N_K = list(map(int,input().split()))

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

B = []
for i in A:
    B.append(i)
sequence=B*N_K[1]
#print(len(tentou))
#for j in range(len(tentou)):
#    num+=tentou[j]*(10**(len(tentou)-1-j))
#print(sequence)
count = 0
for i in range(1,len(sequence),1):
    for j in range(i,len(sequence),1):
        if sequence[i-1] > sequence[j]:
            count += 1


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

Submission status: Runtime Error

Solution code:
class FenwickTree:
    arr = []
    def __init__(self, n):
        self.arr = [0 for _ in range(n + 1)]

    def inc(self, i, val):
        self.private_inc(i + 1, val)

    def sum(self, a, b):
        return self.private_sum(b+1) - self.private_sum(a)

    def private_inc(self, i, val):

        while i < len(self.arr):
            self.arr[i] += val
            i += i & -i

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

MOD = 10 **9 +7
 
N, K = [int(v) for v in raw_input().split()]
A = [int(v) for v in raw_input().split()]
maxA = max(A)
indexInv = [ [] for _ in range(maxA)]
for index, value in enumerate(A):
    indexInv[value-1].append(index)
nbrs = FenwickTree(maxA+1)
dbl = []
inversions = 0
versions = 0
for k in range(maxA):
    for index in indexInv[k]:

        thisInv = nbrs.sum(index, maxA)
        thisVer = nbrs.sum(0, index -1)
        dbl.append((index, thisInv, thisVer))
    #print('Adding doubles ', dbl)
    for val, invV, vers in dbl:
        inversions += invV
        versions += vers
        nbrs.inc(val, 1)
    dbl = []
#print('Inversions =  {} '.format(inversions))
#print('Versions =  {} '.format(versions))
res = ((K + 1) * K)/2 * inversions + (K * (K-1))/2 * versions
res = res % MOD
print(res)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
DIV_NUM = 1000000007


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

tree = [0] * (N+1)

# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x&(-x)
def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x&(-x)
    return s

answer = N*(N-1)//2
for x in A:
    answer -= BIT_sum(tree,x)
    BIT_update(tree,x)

B = sorted(A)

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

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

Submission status: Runtime Error

Solution code:
N,k= map(int,input().split())
A= list(map(int,input().split()))
tree = [0] * (N+1)
M=10**9+7
def BIT_update(tree,x):
  while x <= N:
    tree[x] += 1
    x += x&(-x)
def BIT_sum(tree,x):
  s = 0
  while x:
    s += tree[x]
    x -= x&(-x)
  return s

answer = N*(N-1)//2
c={}
for x in A:
    answer -= BIT_sum(tree,x)
    BIT_update(tree,x)
    if x not in c:
        c[x]=1
    else:
        c[x]+=1
c=sorted(c.items(),key=lambda x:x[0])
d,e=0,0
for j in c:
    d=(d+(((k*(k-1))//2))*e)%M
    e+=j[1]
print((answer*k+d)%M)

Submission status: Runtime Error

Solution code:
import sys

def process(data):
	count = 0

	N = int(data[0][0])
	K = int(data[0][1])
	A = list(map(int, data[1])) * K

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

	count = count % (10**9+7)
	return count



def main():
	d = []
	for i in range(2):
		data = raw_input()
		data = data.split(" ")
		d.append(data)
	print(process(d))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
amax = max(a)
count = [0]*2000
c_in = 0
for i in range(n):
  for j, t in enumerate(a[:i]):
    c_in += int(t > a[i])
    if t > a[i]:
  count[a[i]-1] += 1
c_out = 0
for i in range(n):
  c_out += sum(count[:a[i]-1])
res = int(c_in*k + c_out*k*(k-1)/2)
print(res%(10**9+7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools

DIV_NUM = 1000000007


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

# https://atcoder.jp/contests/chokudai_S001/submissions/5684678
data = [0]*(N+1)
def add(i, x):
    while i <= N:
        data[i] += x
        i += i & -i
def get(i):
    s = 0
    while i:
        s += data[i]
        i -= i & -i
    return s
def su(i,j):
    return get(j)-get(i)
ans = 0
for i,a in enumerate(A):
    add(a, 1)
 
    ans += a-get(a)
answer = ans

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 = (K * answer) + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
a = N*[0]

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

c = [i*K*(K+1)//2 for i in a]
print(sum(c))%(10**9+7)

Submission status: Runtime Error

Solution code:
import math

def bitsum(bit,i):
  s = 0
  while i > 0:
    s += bit[i]
    i -= i&(-i)
  return s

def bitadd(bit,i,x):
  while i <= n[0]*n[1]:
    bit[i] += x
    i += i&(-i)
  return bit
    
n = list(map(int,input().split()))
a = list(map(int,input().split())) * n[1]

#bitの構築
n_ = int(math.log2(n[0]*n[1])) + 1
bit = [0] * (2**n_)
bit.append(0)

ass = 0
for j in range(n[0]*n[1]):
    ass += j-bitsum(bit,a[j])
    bit = bitadd(bit,a[j],1)
    
print(ass % (10**9 + 7))

Submission status: Runtime Error

Solution code:
class FenwickTree:
    arr = []
    def __init__(self, n):
        self.arr = [0 for _ in range(n + 1)]

    def inc(self, i, val):
        self.private_inc(i + 1, val)

    def sum(self, a, b):
        return self.private_sum(b+1) - self.private_sum(a)

    def private_inc(self, i, val):

        while i < len(self.arr):
            self.arr[i] += val
            i += i & -i

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

MOD = 10 **9 +7
 
N, K = [int(v) for v in raw_input().split()]
A = [int(v) for v in raw_input().split()]
indexInv = [ [] for _ in range(N)]
for index, value in enumerate(A):
    indexInv[value-1].append(index)
nbrs = FenwickTree(N)
dbl = []
inversions = 0
versions = 0
for k in range(N):
    for index in indexInv[k]:

        thisInv = nbrs.sum(index, N-1)
        thisVer = nbrs.sum(0, index -1)
        dbl.append((index, thisInv, thisVer))
    #print('Adding doubles ', dbl)
    for val, invV, vers in dbl:
        inversions += invV
        versions += vers
        nbrs.inc(val, 1)
    dbl = []
#print('Inversions =  {} '.format(inversions))
#print('Versions =  {} '.format(versions))
res = ((K + 1) * K)/2 * inversions + (K * (K-1))/2 * versions
res = res % MOD
print(res)

Submission status: Runtime Error

Solution code:
n,k  = (int(i) for i in input().split())
a = [int(j) for j in input().split()]
b = a * k
c = range(0,n+2)
res = 0
for d in c:
 e = range(d,n+2)
 for f in e:
  #print(d,f)
  if b[d] > b[f]:
   #print(b[d],">",b[f])
   res = res + 1
print(res)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:
    def __init__(self, n):
        # 0-indexed
        self.size = n
        self.tree = [0] * (n+1)
 
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s
    
    # 区間和の取得 [l, r)
    def get(self, l, r=None):
        # 引数が1つなら一点の値を取得
        if r is None: r = l+1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    # 値の追加：添字, 値
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

# 1からnまでの等差数列の和
def get_sum(n): return (1+n)*n//2

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

bit = BIT(N+1)
org = 0
for i in range(N-1, -1, -1):
    bit.add(A[i], 1)
    # 自分より右にある、自分より小さな数の個数
    org += bit.sum(A[i]-1)

ans = (org*K + org*get_sum(K-1)) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

    import collections
    count = 0
    for i,a in enumerate(A):
        c = collections.Counter(A[i+1:])

        for co in c.most_common():
            if int(co[0]) < int(A[i]):
                count += co[1]

    print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools

DIV_NUM = 1000000007


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

tree = [0] * (N+1)

# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x&(-x)
def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x&(-x)
    return s

answer = N*(N-1)//2
for x in A:
    answer -= BIT_sum(tree,x)
    BIT_update(tree,x)

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 = (K * answer) + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
import numpy as np

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

B = 0
C = 0

for i in range(N):
    D = A[i::]
    B += np.sum(D < A[i]) % (10**9 + 7)
    C += np.sum(A < A[i]) % (10**9 + 7)
    
E = B * K % (10**9 + 7)
F = C * (np.sum(np.arange(K-1)+1) % (10**9 + 7)) % (10**9 + 7)

print(int((E+F) % (10**9 + 7)))

Submission status: Runtime Error

Solution code:
import numpy as np

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

B = np.zeros(N)
C = np.zeros(N)

for i in range(N):
    D = A[i::]
    B[i] = np.sum(D < A[i]) % (10**9 + 7)
    C[i] = np.sum(A < A[i]) % (10**9 + 7)
    
E = np.sum(B) * K % (10**9 + 7)
F = np.sum(C) * (np.sum(np.arange(K-1)+1) % (10**9 + 7)) % (10**9 + 7)

print(int((E+F) % (10**9 + 7)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
DIV_NUM = 1000000007


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

tree = [0] * (N+1)

# https://atcoder.jp/contests/chokudai_S001/submissions/6789704
def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x&(-x)
def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x&(-x)
    return s

answer = N*(N-1)//2
for x in A:
    answer -= BIT_sum(tree,x)
    BIT_update(tree,x)

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 = (K * answer) + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)

Submission status: Runtime Error

Solution code:
import numpy as np

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

B = np.zeros(N)
C = np.zeros(N)

for i in range(N):
    D = A[i::]
    B[i] = np.sum(D < A[i]) % (10**9 + 7)
    C[i] = np.sum(A < A[i]) % (10**9 + 7)
    
E = np.sum(B) * K % (10**9 + 7)
F = np.sum(C) * np.sum(np.arange(K-1)+1) % (10**9 + 7)

print(int((E+F) % (10**9 + 7)))

Submission status: Runtime Error

Solution code:
import bisect

def BIT_update(tree,x):
  while x <= n:
    tree[x] += 1
    x += x&(-x)
def BIT_sum(tree,x):
  s = 0
  while x:
    s += tree[x]
    x -= x&(-x)
  return s

  
n,k = map(int, input().split())
a = list(map(int, input().split()))
sorted_a = sorted(a)
d = 0
tree = [0] * (n+1)
 

ans = n*(n-1)//2

for x in a:
  ans -= BIT_sum(tree,x)
  BIT_update(tree,x)
  
mod = 10 ** 9 + 7
ans = (ans * k) % mod

for i in a:
  d += bisect.bisect_left(sorted_a, i)

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

B = np.zeros(N)
C = np.zeros(N)

for i in range(N):
    D = A[i::]
    B[i] = np.sum(D < A[i])
    C[i] = np.sum(A < A[i])
    
E = np.sum(B) * K % (10**9 + 7)
F = np.sum(C) * np.sum(np.arange(K-1)+1) % (10**9 + 7)

print(int((E+F) % (10**9 + 7)))

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
target = A * K
count = 0
for i in range(len(target)):
	for j in range(i,len(target)):
		if target[i] > target[j]:
			count += 1



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

Submission status: Runtime Error

Solution code:
#B
n, k =map(int, input().split())
a=list(map(int, input().split()))
b=a*k
count=0
for i in range(0,k*n-1):
    for j in range(i+1,k*n):
        if b[i]>b[j]:
            count+=1
            #print(i,j)
print(count%(1000000000+7))

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
from itertools import permutations,groupby
import sys
import bisect
import string
alp=string.ascii_lowercase
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7
#mo=998244353
#input=sys.stdin.readline

n,k=MI()
a=LI()
c=[0]*(n+1)
t=[0]*(2000+10)
for i in range(n):
    c[a[i]]+=1
    tmp=0
    for j in range(i):
        tmp+=1 if a[j]>a[i] else 0
    t[i]=tmp

A=[0]
for i in c:
    A+=[i+A[-1]]
q=0
for i in range(n):
    q+=A[a[i]]
#q=sum(A[:-1])
q%=mo
q*=k*(k-1)//2
q%=mo

ans=k*sum(t)%mo
ans+=q
print(ans%mo)
#print(c,A,t,ans%mo)

Submission status: Runtime Error

Solution code:
import bisect
n,k=map(int,input().split())
mod=10**9+7;ans=0
a=list(map(int,input().split()))
c=sorted(a)
d=[0]*n
e=[0]*n
for i in range(n):
  d[i]=bisect.bisectleft(c,a[i])
for i in range(n):
  cnt=0
  for j in range(i,n):
    if a[i]>a[j]:
      cnt+=1
  e[i]=cnt
st=sum(e)*k%mod
ad=sum(d)%mod
print((st+(ad*(k-1)*k//2)%mod)%mod)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = a*k
cnt = 0
for i in range(len(b)-1):
  for j in range(i+1,len(b)):
    if b[i] > b[j]:
      cnt += 1
x = 10**9 + 7
print(cnt%x)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
# スペース区切りの整数の入力
N, K = map(int, input().split())
As = list(map(int, input().split())) * K

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

print(count // (pow(10, K) + 7))

Submission status: Runtime Error

Solution code:
import bisect
n,k=map(int,input().split())
mod=10**9+7;ans=0
a=list(map(int,input().split()))
c=sorted(a)
d=[0]*n
e=[0]*n
for i in range(n):
  d[i]=bisect.bisectleft(c,a[i])
for i in range(n):
  cnt=0
  for j in range(i,n):
    if a[i]>a[j]:
      cnt+=1
  e[i]=cnt
st=sum(e)*k%mod
ad=sum(d)%mod
print((st+(ad*(k-1)*k//2)%mod)%mod)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
from itertools import permutations,groupby
import sys
import bisect
import string
alp=string.ascii_lowercase
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7
#mo=998244353
#input=sys.stdin.readline

n,k=MI()
a=LI()
c=[0]*(n+1)
t=[0]*(n+1)
for i in range(n):
    c[a[i]]+=1
    tmp=0
    for j in range(i):
        tmp+=1 if a[j]>a[i] else 0
    t[i]=tmp

A=[0]
for i in c:
    A+=[i+A[-1]]
q=0
for i in range(n):
    q+=A[a[i]]
#q=sum(A[:-1])
q%=mo
q*=k*(k-1)//2
q%=mo

ans=k*sum(t)%mo
ans+=q
print(ans%mo)
#print(c,A,t,ans%mo)

Submission status: Runtime Error

Solution code:
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())))*k
print(int(bubble_sort(a)%(1e9+7)))

Submission status: Runtime Error

Solution code:
import bisect
n,k = map(int,input().split())
a = list(map(int,input().split()))

# i が与えられたとき a1~aiまでの和を計算する( O(log n) )
def bitsum(bit,i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i&(-i)
    return s
    
# i と x が与えられたとき ai += x とする ( O(log n) )
def bitadd(bit,i,x):
    while i <= n:
        bit[i] += x
        i += i&(-i)
    return bit
    
#################################
import math

#bitの構築
n_ = int(math.log2(n)) + 1
bit = [0] * (2**n_)
bit.append(0)

################################
ass = 0
for j in range(n):
    ass += j-bitsum(bit,a[j])
    #bitsum(bit,a[j]): j-1番目までの中でa[j]以下のもの
    bit = bitadd(bit,a[j],1)

res = 0
b = sorted(a)

for e in b:
    kw = bisect.bisect_right(b,e)
    res += n-kw

mod = 10**9+7

print((k*ass%mod+res*k*(k-1)//2%mod)%mod)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    m,d = LI()
    ans = 0
    for i in range(1,m+1):
        for j in range(1,d+1):
            d1 = j%10
            d2 = j//10
            if d1 >= 2 and d2 >= 2 and d1*d2 == i:
                ans += 1
    print(ans)
    return

#B
def B():
    def add(i):
        while i <= n:
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n,k = LI()
    a = LI()
    bit = [0]*(n+1)
    ans = 0
    for i in range(n):
        ans += (i-sum(a[i]))*k
        add(a[i])
    inv = pow(2,mod-2,mod)
    for i in range(n):
        ans += sum(a[i]-1)*k*(k-1)*inv%mod
    print(ans%mod)
    return

#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    B()