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 = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9 + 7

LANK = list(set(A))
LANK.sort()
LANK2 = [0] * 2000
for i, l in enumerate(LANK):
    LANK2[l] = i

LANK = [-1] * N
for i,a in enumerate(A):
    LANK[i] = LANK2[a]

back = [0] * N
for i,a in enumerate(A[::-1]):
    cnt = 0
    for j,a2 in enumerate(A[::-1]):
        if i > j and a > a2:
            cnt += 1
    back[N-1-i] = cnt
    
SUM = 0
tmp = K*(K-1) //2
tmp %= MOD

for i,a in enumerate(A):
    SUM += (LANK[i] * tmp)%MOD
    SUM += (back[i] * K)%MOD
    SUM %= MOD
print(SUM)

Submission status: Runtime Error

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

LANK = list(set(A))
LANK.sort()
LANK2 = [0] * 2000
for i, l in enumerate(LANK):
    LANK2[l] = i

LANK = [-1] * N
for i,a in enumerate(A):
    LANK[i] = LANK2[a]

back = [0] * N
for i,a in enumerate(A[::-1]):
    cnt = 0
    for j,a2 in enumerate(A[::-1]):
        if i > j and a > a2:
            cnt += 1
    back[N-1-i] = cnt
    
SUM = 0
tmp = K(K-1)//2
tmp %= MOD
# print('a')
for i,a in enumerate(A):
    SUM += (LANK[i] * tmp)%MOD
    SUM += (back[i] * K)%MOD
    SUM %= MOD
print(SUM)

Submission status: Runtime Error

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

LANK = list(set(A))
LANK.sort()
LANK2 = [0] * 2000
for i, l in enumerate(LANK):
    LANK2[l] = i

LANK = [-1] * N
for i,a in enumerate(A):
    LANK[i] = LANK2[a]

back = [0] * N
for i,a in enumerate(A[::-1]):
    cnt = 0
    for j,a2 in enumerate(A[::-1]):
        if i > j and a > a2:
            cnt += 1
    back[N-1-i] = cnt
    

SUM = 0
tmp = sum(range((K)))
for i,a in enumerate(A):
    SUM += LANK[i] * tmp + back[i] * K
    SUM %= MOD
print(SUM)

Submission status: Runtime Error

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

LANK = list(set(A))
LANK.sort()
print(LANK)
LANK2 = [0] * 2000
for i, l in enumerate(LANK):
    LANK2[l] = i

LANK = [-1] * N
for i,a in enumerate(A):
    LANK[i] = LANK2[a]

back = [0] * N
for i,a in enumerate(A[::-1]):
    cnt = 0
    for j,a2 in enumerate(A[::-1]):
        if i > j and a > a2:
            cnt += 1
    back[N-1-i] = cnt
    

SUM = 0
tmp = sum(range((K)))
for i,a in enumerate(A):
    SUM += LANK[i] * tmp + back[i] * K
    SUM %= MOD
print(SUM)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
A = list(map(int,input().split()))
B = A*k
lA = len(A)
lB = len(B)
mod=10**9+7
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
print((cnt1*k+cnt2*(k*(k-1)//2))%mod)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a = list(map(int,input().split()))
B = a*k
lB = len(B)
mod=10**9+7
cnt=0
for i in range(lB):
    for j in range(i+1,lB):
        if B[i] > B[j]:
            cnt+=1
print(cnt%mod)

Submission status: Runtime Error

Solution code:
import sys


def main():
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split())) * K

    count = 0

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

    ans = count % 1000000007
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys


def main():
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split())) * K

    tree = [0] * (K * N + 1)
    count = 0

    for i in A:
        tree[i] = tree[i] + 1
        count = count + sum(tree[i + 1 :])

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys


def main():
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split())) * K

    count = 0

    for i, n in enumerate(A):
        for j, m in enumerate(A):
            if i <= j:
                break
            elif m > n:
                count = count + 1

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split())) * K


def main():
    count = 0
    for i in range(0, K * N - 1):
        for j in range(1, K * N):
            if i < j and A[i] > A[j]:
                count = count + 1

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split())) * K

count = 0

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

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

Submission status: Runtime Error

Solution code:
#第一回日本最強プログラマー学生選手権-予選- -B Kleene Inversion
"""
リストをk回繰り返したものの、転倒数の個数を求めよ
先ず純粋に与えられたリスト内での転倒数を求めた後、
それを1~k倍したものを足し合わせる
"""
import sys
sys.setrecursionlimit(1000000)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

class BinaryIndexedTree():
    def __init__(self, seq):
        self.size = len(seq)
        self.depth = self.size.bit_length()
        self.build(seq)
        
    def build(self,seq):
        data = seq
        size = self.size
        for i,x in enumerate(data):
            j = i+(i&(-i))
            if j < size:
                data[j] += data[i]
        self.data = data
        
    def __repr__(self):
        return self.data.__repr__()
        
    def get_sum(self,i):
        data = self.data
        s = 0
        while i:
            s += data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        data = self.data
        size = self.size
        while i < size:
            data[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        data = self.data; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + data[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
#バブルソート(隣り合う2数を入れ替えて順列を昇順にする時の最小手数) 
def Inversion(seq):
    # seqは、1,2,...,Nの順列
    N = len(seq)
    bit = BinaryIndexedTree([0] * (N+1))
    inv = N*(N-1)//2
    for x in seq:
        inv -= bit.get_sum(x)
        bit.add(x,1)
    return inv

res = Inversion(lst1)
#lst全体で見た時にそれより小さい値がいくつあるか
res2 = Inversion(sorted(lst1,reverse=True))
def reydeoro(n):
    return n*(n+1)//2
print((res*k+res2*reydeoro(k-1))%mod)

Submission status: Runtime Error

Solution code:
#第一回日本最強プログラマー学生選手権-予選- -B Kleene Inversion
"""
リストをk回繰り返したものの、転倒数の個数を求めよ
先ず純粋に与えられたリスト内での転倒数を求めた後、
それを1~k倍したものを足し合わせる
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7

n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

class BinaryIndexedTree():
    def __init__(self, seq):
        self.size = len(seq)
        self.depth = self.size.bit_length()
        self.build(seq)
        
    def build(self,seq):
        data = seq
        size = self.size
        for i,x in enumerate(data):
            j = i+(i&(-i))
            if j < size:
                data[j] += data[i]
        self.data = data
        
    def __repr__(self):
        return self.data.__repr__()
        
    def get_sum(self,i):
        data = self.data
        s = 0
        while i:
            s += data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        data = self.data
        size = self.size
        while i < size:
            data[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        data = self.data; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + data[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
#バブルソート(隣り合う2数を入れ替えて順列を昇順にする時の最小手数) 
def Inversion(seq):
    # seqは、1,2,...,Nの順列
    N = len(seq)
    bit = BinaryIndexedTree([0] * (N+1))
    inv = N*(N-1)//2
    for x in seq:
        inv -= bit.get_sum(x)
        bit.add(x,1)
    return inv

res = Inversion(lst1)
#lst全体で見た時にそれより小さい値がいくつあるか
res2 = Inversion(sorted(lst1,reverse=True))
def reydeoro(n):
    return n*(n+1)//2
print((res*k+res2*reydeoro(k-1))%mod)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> vec(n);
    for ( int i = 0; i < n; ++i ) {
        cin >> vec.at(i);
    }

    long long count1 = 0;
    for ( int i = 0; i < n; ++i ) {
        for ( int j = i+1; j < n; ++j ) {
            if ( vec.at(i) > vec.at(j)) {
                count1++;
            }
        }
    }

    long long count2 = 0;
    for ( int i = 0; i < n; ++i ) {
        for (int j = 0; j < n; ++j ) {
            if ( i != j && vec.at(i) > vec.at(j)) {
                count2++;
            }
        }
    }
    cout << count1 << " " << count2 << endl;

    count2 *= k;
    count2 %= 1000000007;
    count2 *= (k-1);
    count2 /= 2;
    count2 %= 1000000007;

    long long ans = count1 * k;
    ans %= 1000000007;
    ans += count2;
    ans %= 1000000007;

    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
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):
        # [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: # idx1が偶数
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: # idx2が奇数
                    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)
    num += st.query(a+1, max_a+1)

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

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

Submission status: Runtime Error

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

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

    # add x to i
    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(len(X)+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)

Submission status: Runtime Error

Solution code:
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):  # 区間 [1, i]の和
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):  # iにxを加算
        while i <= self.size:
            self.tree[i] += x
            i += i & -i  
    def pos(self, idx):  # idxの値を取得
        return self.sum(idx) - self.sum(idx-1)
    def lower_bound(self, w):  # w以上の値を持つ最小のidxを検索
        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(N)
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)

Submission status: Runtime Error

Solution code:
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int MOD = 1e9 + 7;

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	ll k;
	cin >> n >> k;
	k--;
	vi a(n);
	rep(i, n) cin >> a[i];
	ll ans = 0;
	rep(i, n) rep(j, n) if(a[i] > a[j]){
		int f = (i < j);
		if(f) k++;
		(ans += (ll)(k * (k + 1)) / 2) %= MOD;
		if(f) k--;
	}
	cout << ans % MOD << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/

Submission status: Runtime Error

Solution code:
from sys import stdin

n, k = map(int, stdin.readline().rstrip().split())
a = map(int, stdin.readline().rstrip().split())

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
 
bit = Bit(n*k)
ans = 0
a = list(a)*k
for i, p in enumerate(a):
    ans += (i - bit.sum(p)) % (10^9+7)
    bit.add(p, 1)
print(ans)

Submission status: Runtime Error

Solution code:
import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
bit=[0 for i in range(N+1)]
bitbit=[0 for j in range(N+1)]
pn=10**9+7
ten=0
tenten=[]
for i in range(N):
    bit[A[i]-1]+=1
    for j in range(A[i],N):
        ten+=bit[j]
for i in range(N):
    bitbit[i]=sum(bit[i+1:N])
#print(ten)
#print(bit)
#print(bitbit)
print(int(((K-1)*(K)/2*(sum(bitbit)%pn)%pn+K*(ten%pn))%pn))

Submission status: Runtime Error

Solution code:
import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
bit=[0 for i in range(N)]
bitbit=[0 for j in range(N)]
pn=10**9+7
ten=0
tenten=[]
for i in range(N):
    bit[A[i]-1]+=1
    for j in range(A[i],N):
        ten+=bit[j]
for i in range(N-1):
    bitbit[i]=sum(bit[i+1:N])
#print(ten)
#print(bit)
#print(bitbit)
print(int(((K-1)*(K)/2*(sum(bitbit)%pn)%pn+K*(ten%pn))%pn))

Submission status: Runtime Error

Solution code:
import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
bit=[0 for i in range(N)]
bitbit=[0 for j in range(N)]
pn=10**9+7
ten=0
tenten=[]
for i in range(N):
    bit[A[i]-1]+=1
    for j in range(A[i],N):
        ten+=bit[j]
for i in range(N):
    bitbit[i]=sum(bit[i+1:N])
#print(ten)
#print(bit)
#print(bitbit)
print(((K-1)*(K)/2*(sum(bitbit)%pn)%pn+K*(ten%pn))%pn)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
ans=0
C=[0 for _ in range(N+1)]
for i in range(N-1):
    for j in range(i+1,N):
        a=A[j]-A[i]
        if a<0:
            #ans+=1
            C[A[i]]+=1
D=[0 for i in range(N+1)]
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        a=A[i]-A[j]
        if a>0:
            D[A[i]]+=1
x=A[0]-A[-1]
if x<0:
    #ans+=1
    C[A[0]]+=1
for i in range(len(C)):
    a=K*C[i]%MOD
    ans+=a
k=(K*(K-1))//2
k=k%MOD
for i in range(len(D)):
    b=k*D[i]%MOD
    ans+=b
print(ans%MOD)

Submission status: Runtime Error

Solution code:
mod=(10**9)+7
def main():
    t=int(input())
    for _ in range(t):
        n,k=map(int,input().split())
        arr=[int(x) for x in input().split()]
        t1=t2=0
        for i in range(len(arr)):
            for j in range(len(arr)):
                if i <j:
                    if arr[i] > arr[j]:
                        t1+=1
        narr=arr*2
        for i in range(len(arr)):
            for j in range(len(arr),len(narr)):
                if narr[i] > narr[j]:
                    t2+=1
                    
        ans=(t1*k)+(t2*k*(k-1)/2)
        print(ans%mod)
main()

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
sl=sorted(l)
ten=0
for i in range(n):
    for j in range(n):
        if l[i]>l[j]and i<j:ten+=1
pre=sl[0]
jiten=0
c=0
for i,x in enumerate(sl):
    if x==pre:jiten+=c
    else:
        jiten+=i
        c=i
        pre=x

print(ten*k+jiten*(k*(k-1))//2)n,k=map(int,input().split())
l=list(map(int,input().split()))
sl=sorted(l)
ten=0
for i in range(n):
    for j in range(n):
        if l[i]>l[j]and i<j:ten+=1
pre=sl[0]
jiten=0
c=0
for i,x in enumerate(sl):
    if x==pre:jiten+=c
    else:
        jiten+=i
        c=i
        pre=x

print(ten*k+jiten*(k*(k-1))//2)

Submission status: Runtime Error

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    #A内での転倒数t1
    bit = BinaryIndexedTree(N)
    t1 = Mint()
    for i,a in enumerate(reversed(A)):
        t1 += bit.query(a-1)
        bit.add(a,1)
    
    #ひとつ左のAへの転倒数t2
    t2 = Mint()
    for a in A:
        t2 += bit.query(a-1)

    K2 = K * (K - 1) // 2
    ans = t1 * K + t2 * K2
    print(ans)

class BinaryIndexedTree:
    def __init__(self, n=None, f=lambda x,y:x+y, zero=0, initial_values=None):
        assert(n or initial_values)
        self.__f, self.__z, = f, zero
        self.__n = n if n else len(initial_values)
        self.__dat = [zero] * (self.__n + 1)
        if initial_values:
            for i in range(1, self.__n + 1): self.add(i, initial_values[i-1]) #slow

    def add(self, i, v):
        i += 1
        while i <= self.__n:
            self.__dat[i] = self.__f(self.__dat[i], v)
            i += -i&i

    def query(self, r):
        r += 1
        ans = self.__z
        while r:
            ans = self.__f(ans, self.__dat[r])
            r -= -r&r
        return ans
    
class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
  
  n,k=map(int,input().split())
  a=list(map(int,input().split()))
  
  count=lambda arr,now:sum(element<now for element in arr)
  b=[[count(a[:i],a[i]),count(a[i+1:],a[i])] for i in range(n)]

  ans=0
  prime=10**9+7
  
  for x in b:
    left=x[0]
    right=x[1]
    res=(k-1)*k//2*(right+left)+right*k
    ans+=res%prime
    
  print(ans%prime)

  if __name__=="__main__":
  main()

Submission status: Runtime Error

Solution code:
from itertools import combinations, accumulate
n,m = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
ls = [0]*2001
for i in a:
  ls[i] += 1
accls = list(accumulate(a))
for i,j in combinations(a,2):
  if i>j:
    ans += 1
for i in range(1,2001):
  if ls[i]>=1:
    ans = (ans + accls[i-1]*(m-1))%mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7
from scipy.special import comb

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, k = na()
a = na()
cl = 0
cr = 0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i] < a[j]:
            cl += 1
        if a[i] > a[j]:
            cr += 1
ans = (cr*k %mod + (cl+cr) * comb(k, 2, exact=True)) % mod
print(ans)

Submission status: Runtime Error

Solution code:
def count_inversion(sequence):
  return sum(sum(m<n for m in sequence[i+1:]) for i,n in enumerate(sequence))
n,k = map(int,input().split())
a = lsit(map(int,input().split()))
print(count_inversion(a*2)%10**9+7)

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors
def examA():
    M, D = LI()
    c = D//10
    ans = 0
    for i in range(2,M+1):
        d = make_divisors(i)
#        print(d)
        for j in range(len(d)//2):
            cur0 = d[j*2+1]; cur10 = d[j*2]
            if cur10==1:
                continue
            if cur0<=9:
                if cur10<c:
                    ans +=1
#                    print(cur10,cur0)
                elif cur10==c and cur0+cur10*10<=D:
                    ans +=1
#                    print(cur10,cur0)
        for j in range(len(d) // 2):
            cur0 = d[j * 2];cur10 = d[j * 2+1]
            if cur0 == 1:
                continue
            if cur10 <= 9:
                if cur10 < c:
                    ans += 1
                elif cur10 == c and cur0 + cur10 * 10 <= D:
                    ans += 1
        if len(d)%2==1:
            cur0 = d[-1]; cur10 = d[-1]
            if cur10==1:
                continue
            if cur0<=9:
                if cur10<c:
                    ans +=1
#                    print(cur10,cur0)
                elif cur10==c and cur0+cur10*10<=D:
                    ans +=1
#                    print(cur10,cur0)
    print(ans)
    return

class Bit():
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        return
    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
        return
def examB():
    N, K = LI()
    A = LI()
    d = defaultdict(int)
    bit = Bit(N)
    cur = 0
    for i, a in enumerate(A):
        bit.add(a, 1)
        cur += i + 1 - bit.sum(a)
    As = 0
    for i in A:
        d[i] +=1
    A.sort()
    for i in range(N):
        As += max(0,i-d[A[i]]+1)
#    print(cur,As)
    ans = (As*(K**2) - (As -2*cur)*K)//2
    ans =int(ans)%mod
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()

Submission status: Runtime Error

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

nums = []
nums_2 = []
for i in range(N):
  num = int(A[i])
  s = 0
  k = 0
  for j in range(i,N):
    if A[j] < num:
      s += 1
  nums.append(s)
  for t in range(N):
    if A[t] < num:
      k += 1
  nums_2.append(k)

result = 0
for i in range(N):
  result += ((K*(K-1))/2)*(nums_2[i]) + K*nums[i]


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

nums = []
nums_2 = []
for i in range(N):
  num = int(A[i])
  s = 0
  k = 0
  for j in range(i,N):
    if A[j] < num:
      s += 1
  nums.append(s)
  for t in range(N):
    if A[t] < num:
      k += 1
  nums_2.append(k)

result = 0
for i in range(N):
  result += ((K*(K-1))/2)*(nums_2[i]) + K*nums[i]

print(int(result/(10**9+7)))

Submission status: Runtime Error

Solution code:
def Kleene(a, k):
  if k==1:
    count = 0
    for i in range(len(a)-1):
      for j in range(i+1, len(a)):
        if a[i] > a[j]:
          count += 1
    return count
  
  else:
    a.sort()
    l = [ i for i in range(len(a)) ]
    for i in range(1, len(a)):
      if a[i] == a[i-1]:
        l[i] = l[i-1]
    count = sum(l) * (k-1)
    return ( Kleene(a, 1) + Kleene(a, k-1) + count ) % 1000000007

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

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a_array = [int(x) for x in input().split()]
INF = 10**9+7

cnt_array = [0 for x in range(n+1)]
a_array2 = []
ans = 0
for a in a_array:
    cnt_array[a] += 1
    a_array2.append(sum(cnt_array[a+1:]))
a_array3 = []
for i in a_array:
    tmp = 0
    for j in a_array[::-1]:
        if j > i:
            tmp += 1
    a_array3.append(tmp)
for cnt, d in zip(a_array2, a_array3):
    ans += (k*(2*cnt+(k-1)*d))//2
    ans = ans % INF
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
AN = map(str, input().split())
number_list = list(AN ) * K
count =0
for i in range(len(number_list)):
    for j in range(len(number_list)-1,i,-1):
        if number_list[j] < number_list[j-1]:
            number_list[j],number_list[j-1] = number_list[j-1],number_list[j]
            count +=1
count %= (10**9 + 7)
print(count)

Submission status: Runtime Error

Solution code:
n,k=[int(x) for x in input().split()
a=[int(x) for x in input().split()]
ct=0
for i in range(n):
     for j in range(i,n):
     	if a[j]<a[i]: ct+=1
print((((k*k-k)/2)*ct)%1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools
INF = float('inf')
mod = 10**9+7

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(N+1)]
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
bit = BIT(N+1)
cnt = 0
for a in A:
    cnt += bit.sum(N)-bit.sum(a)
    bit.add(a, 1)
X = 0
for a in A:
    X += bit.sum(a-1)
print((cnt*K+X*(K-1)*K//2)%mod)