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: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
# @author 

import sys

class BKleeneInversion:
    def solve(self):
        MOD = 10 ** 9 + 7

        n, k = [int(_) for _ in input().split()]
        a = [int(_) for _ in input().split()]
        s = [0] * n
        t = [0] * n
        for i in range(n):
            for j in range(i):
                if a[j] < a[i]:
                    t[i] += 1
            for j in range(i + 1, n):
                if a[j] < a[i]:
                    s[i] += 1
                    t[i] += 1

        # print(s, t)

        ans = k * sum(s) + k ** 2 * sum(t) - (k * (k + 1)) * sum(t) // 2
        ans %= MOD
        print(ans)

solver = BKleeneInversion()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

class BIT: #0-indexed
    def __init__(self, n):
        self.tree = [0]*(n+1)
        self.tree[0] = None
#        self.element = [0]*(n+1)
    def sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def range(self,l,r): #a_l + ... + a_r 閉区間
        return sum(r) - sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= n:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
     
###########################################
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意
 
#n = int(input())
n,k = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]
 
sA = sorted(a)
# def zaatu(x): return bisect_left(sA, x) #xの圧縮先
# def modosu(i): return sA[i]  # 逆写像
 
b = BIT(n)
 
from bisect import *
res = [0]*n
for i,ai in enumerate(a):
    j = bisect_left(sA, ai)
    res[i] = i - b.sum(j)
    b.add(j,1)
 
#print(res)

MOD = 10**9 + 7
ans = 0
for i,ai in enumerate(a):
    ans += k*res[i]
    ans %= MOD
    j = bisect_left(sA, ai)
    ans += (k*(k-1)//2%MOD)*(n - b.sum(j))
    ans %= MOD
    

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
As = list(map(int, input().split()))
r = 0
for i in range(N):
  A = As[i]
  a = len(list(filter(lambda A2: A2 < A, As[:i])))
  b = len(list(filter(lambda A2: A2 < A, As[i+1:])))
  #print(a, b)
  r = (r+a*(K-1)*K//2)%1000000007
  r = (r+b*(K+1)*K//2)%1000000007
print(r)

Submission status: Accepted

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

Submission status: Accepted

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

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

A.extend(A)

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

print(((K * (K - 1) // 2) * b + K * a) % (10**9 + 7))

Submission status: Accepted

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

class Bit(object):
    def __init__(self):
        self.bit = [0] * 2001

    def add(self, i):
        while i <= 2000 and i >= 1:
            self.bit[i] += 1
            i += i & -i

    def query(self, i):
        ans = 0
        while i <= 2000 and i >= 1:
            ans += self.bit[i]
            i -= i & -i
        return ans

gl, suf = Bit(), Bit()

for i in range(n):
    gl.add(a[i])

ans = 0

for i in range(n - 1, -1, -1):
    u = suf.query(a[i] - 1)
    v = gl.query(a[i] - 1)
    ans += (u + (u + v * (k - 1))) * k // 2
    suf.add(a[i])

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
MOD = 10**9+7
K1 = ((K-1)*(K)//2)%MOD
K2 = ((K+1)*(K)//2)%MOD
for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            ans += K1
    for j in range(i+1,N):
        if A[i] > A[j]:
            ans += K2
print(ans%MOD)

Submission status: Accepted

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

ans = 0
S = [0]*N
T = [0]*N
for i, a in enumerate(A):
    for j, a_ in enumerate(A):
        if a_<a: S[i]+=1
        if j>i and a_<a: T[i]+=1

print((K*(K-1)//2*sum(S) + sum(T)*K)%(10**9+7))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

MOD = 10**9+7

def main():
    n, k = rli()
    la = rli()
    rev1 = 0
    rev2 = 0
    for i in range(len(la)):
        for j in range(len(la)):
            if la[i] > la[j]:
                if i < j:
                    rev1 += 1
                else:
                    rev2 += 1
    ans = rev1 * k*(k+1)//2 + rev2 * (k-1)*k//2
    ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
mod = 10**9+7
cnt = 0
for ind,a in enumerate(A):
    cnt_l = 0
    cnt_r = 0
    for ind2,b in enumerate(A):
        if(ind==ind2):
            continue
        if(ind<ind2):
            if(a>b):
                cnt_r += 1
        if(ind>ind2):
            if(a>b):
                cnt_l += 1
    cnt += cnt_r*(K*(K+1)//2)
    cnt += cnt_l*((K-1)*K//2)
    cnt %= mod
print(cnt)

Submission status: Accepted

Solution code:
mod = 10**9+7
n,k = map(int, input().split())
a = list(map(int, input().split()))
b = [0]*2001
for i in a:
    b[i] += 1
for i in range(2000):
    b[i+1] += b[i]

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

Submission status: Accepted

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 <= m:
            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()
    m = 2000
    a = LI()
    bit = [0]*(m+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():
    n = I()

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
tentou = []
tentou_all = []
for i in range(N):
    now = a[i]
    count = 0
    for j in range(i+1, N):
        if now > a[j]:
            count += 1
    tentou.append(count)

for i in range(N):
    now = a[i]
    count = 0
    for j in range(N):
        if now > a[j]:
            count += 1
    tentou_all.append(count)

ans = 0
for i in range(N):
    x = tentou[i] + tentou_all[i]*(K-1)
    y = tentou[i]
    ans += (K*(x+y))//2
    ans %= 1000000007

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(N):
    a = A[i]
    s1 = 0
    s2 = 0
    for j in range(N):
        if a > A[j]:
            s2 += 1
    for j in range(i, N):
        if a > A[j]:
            s1 += 1
    ans = (ans + K*s1 + (K-1)*K//2*s2)%mod

print(ans)

Submission status: Accepted

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

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
            else:
                ans += (k-1)*k//2
            ans %=10**9+7
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
P = 10**9+7
a = 0
b = 0
for i in range(N):
    for j in range(i):
        if A[i] < A[j]:
            a += 1
for i in range(N):
    for j in range(N):
        if A[i] < A[j]:
            b += 1

print((a*K+b*K*(K-1)//2)%P)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,K = inpl()
aa = inpl()
cnts = [0]*2005

izyos = [0]*N

for i,a in enumerate(aa):
    izyos[i] = sum(cnts[a+1:])
    cnts[a] += 1

sums = [0]*N
for i,a in enumerate(aa):
    sums[i] = sum(cnts[a+1:])

ans = sum(izyos)*K+sum(sums)*((K-1)*K//2)%mod
ans %= mod
print(ans)

Submission status: Accepted

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

MOD = 10**9 + 7

ans = 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(i):
        if a[i] > a[j]:
            y += 1

    ans += x * k * (k + 1) // 2
    ans %= MOD
    ans += y * (k-1) * k // 2
    ans %= MOD
    # print(i, x, y)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int, K: int, A: "List[int]"):
    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
            tmp = 0
            if A[i] > A[j]:
                tmp = K * (K + 1) // 2
            elif A[i] < A[j]:
                tmp = (K - 1) * K // 2
            ret += tmp
            ret %= MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N-1-0+1) ]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def s_list(): return list(input())
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]#NumberGrid
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]

n, k = wi()
a = wi()

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            if arr[j] < arr[i]:
                ans += k
        for j in range(n):
            if arr[j] < arr[i]:
                ans += (k * (k - 1) >> 1) % 1000000007
        ans %= 1000000007
    print(ans % 1000000007)
    
    return 0

main()

Submission status: Accepted

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

ans = 0
for i, ai in enumerate(a):
    left = 0
    right = 0
    for j in range(i):
        if ai > a[j]:
            left += 1
    for j in range(i + 1, n):
        if ai > a[j]:
            right += 1
    ans += (k * (k + 1) * right // 2) + (k * (k - 1) * left // 2)
print(ans % 1000000007)

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,K = II()
A = III()

r = [0]*N
l = [0]*N

for i in range(N):
    for j in range(i+1,N):
        if A[j]<A[i]:
            r[i] += 1
    for j in range(i):
        if A[j]<A[i]:
            l[i] += 1

ans = 0

for i in range(N):
    ans += r[i]*K*(K+1)//2
    ans %= mod
    ans += l[i]*(K-1)*K//2
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include<algorithm>
#define intt long long
const intt NUM = 1000000007;

int main(){
	intt N{}, K{}, initi{}, initi2{}; std::cin >> N >> K;
	std::vector<intt> A(N); for (auto& r : A) { std::cin >> r; }
	for (intt i = 0; i < N - 1; ++i) for (intt j = i + 1; i < N; ++i) if (A[i] > A[j]) {++initi; initi %= NUM;}
	for (intt i = 0; i < N; ++i) for (intt j = 0; j < N; ++j) if (A[i] > A[j]) { ++initi2; initi2 %= NUM; }
	std::cout << ((((initi % NUM) * K) % NUM) + ((initi2 % NUM) * (((K * (K - 1)) % NUM) / 2) ) % NUM)<< std::endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include<algorithm>
#define intt long long
const intt NUM = 1000000007;

int main(){
	intt N, K, initi, initi2{}; std::cin >> N >> K;
	std::vector<intt> A(N); for (auto& r : A) { std::cin >> r; }
	for (intt i = 0; i < N - 1; ++i) for (intt j = i + 1; i < N; ++i) if (A[i] > A[j]) {++initi; initi %= NUM;}
	for (intt i = 0; i < N; ++i) for (intt j = 0; j < N; ++j) if (A[i] > A[j]) { ++initi2; initi2 %= NUM; }
	std::cout << ((((initi % NUM) * K) % NUM) + ((initi2 % NUM) * (((K * (K - 1)) % NUM) / 2) ) % NUM)<< std::endl;
	return 0;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
total_1 = 0
for i in range (n - 1):
    for j in range (i, n):
        if a[i] > a[j]:
            total_1 += 1
total_2 = 0
for i in range (n):
    for j in range (i):
        if a[i] > a[j]:
            total_2 += 1
def factorial(n):
    total = 0
    while(n > 0):
        total += n
        n -= 1
    return total

print(total_1 * K + total_2 * factorial(K - 1))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
print(sum((r+((sum(a[i]>j for j in a[i:])*(k*(k+1)//2)%mod)+(sum(a[i]>j for j in a[:i+1])*(k*(k-1)//2)%mod))%mod)%mod for i in range(n)))

Submission status: Runtime Error

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

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = BIT(n)
count = [0]*(2001)
t = []
for i in range(n):
    x = a[i]
    count[x] += 1
    t.append(i-bit.sum(x))
    bit.add(x,1)

for i in range(1,2001):
    count[i] += count[i-1]

ans = 0
for i in range(n):
    x = k*(2*t[i]+(k-1)%mod*count[a[i]-1])//2
    ans = (ans+x)%mod
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    
    c = Counter(A).most_common()

    if c[0][0] == "0" and c[0][1] == N:
        print("Yes")
    elif len(c) == 2 and c[0][1] == 2*N//3 and c[1][0] == "0" and c[1][1] == N//3:
        print("Yes")
    elif len(c) == 3 and int(c[0][0])^int(c[1][0]) == int(c[2][0]) and c[0][1] == c[1][1] and c[1][1] == c[2][1]:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def cin():  return list(map(int,input().split()))

N, K = cin()
A = cin()

cnt1 = 0
l = len(A)
for i in range(l):
    for j in range(i + 1, l):
        cnt1 += (A[i] > A[j])
        
AA = A + A
l = len(AA)
cnt2 = 0
for i in range(l):
    for j in range(i + 1, l):
        cnt2 += (AA[i] > AA[j])

ans = K * cnt1 + (cnt2 - 2 * cnt1) * K * (K - 1) // 2
print(ans % INF)

Submission status: Runtime Error

Solution code:
N, K = cin()
A = cin()

cnt1 = 0
l = len(A)
for i in range(l):
    for j in range(i + 1, l):
        cnt1 += (A[i] > A[j])
        
AA = A + A
l = len(AA)
cnt2 = 0
for i in range(l):
    for j in range(i + 1, l):
        cnt2 += (AA[i] > AA[j])

ans = K * cnt1 + (cnt2 - 2 * cnt1) * K * (K - 1) // 2
print(ans % INF)

Submission status: Runtime Error

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

cnt = [0] * N
ex = [0] * N
for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            cnt[i] += 1
for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            ex[i] += 1

ans = 0
for i in range(N):
    ans += cnt[i] * ((K + 1) * K // 2) % MOD
for i in range(N):
    ans -= ex[i] * K
print(ans % MOD)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD=10**9+7
n,m=map(int,input().split())
a=set([int(input()) for _ in range(m)])
if 1 in a:
  ans=[1,0]
else:
  ans=[1,1]

@lru_cache(maxsize=None)
def cnt(x):
  if x<2:
    return ans[x]
  if x in a:
    return 0
  else:
    return (cnt(x-1)+cnt(x-2))%MOD

print(cnt(n))

Submission status: Runtime Error

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

mod = 10**9+7

n,k = nm()
a=nl()
b=[0]*(k*n)
for i in range(k):
  for j in range(n):
    b[i*n+j]= a[j]

ans=0

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

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math
 
# import copy
from bisect import bisect_left, bisect_right
# import heapq
 
# sys.setrecursionlimit(1000000)
 
# input aliases
input = sys.stdin.readline
 
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]
 
INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
 
class Segtree_op():
     def __init__(self, n):
         self.size = 1
         while(n >= 1):
             self.size = self.size << 1
             n = n//2
 
         self.arr = [self.unit() for i in range(self.size*2)]
 
     def op(self, lch, rch):
         # update min with holding index
         return lch + rch
 
     def unit(self):
         return 0
 
     def update(self, k, val):
         k += self.size - 1
         self.arr[k] = val
         while(k):
             k = (k - 1) // 2
             self.arr[k] = self.op(self.arr[k*2 + 1], self.arr[k*2 + 2])
 
     def query(self, l, r):
         L = l + self.size
         R = r + self.size
         s = self.unit()
         while L < R:
             if R & 1:
                 R -= 1
                 s = self.op(s, self.arr[R - 1])
 
             if L & 1:
                 s = self.op(s, self.arr[L - 1])
                 L += 1
             L >>= 1
             R >>= 1
         return s
 
 
     def show(self):
         idx = 1
         while(idx <= self.size):
             print(self.arr[idx - 1:idx * 2 - 1])
             idx *= 2
def tento(nums):
    n = len(nums)
    st = Segtree_op(n)
    ret = 0
    for i, num in enumerate(nums):
        st.update(num, st.query(num, num+1)+1)
        # st.show()
        ret += i - st.query(0, num+1) + 1

    return ret



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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####MakeDivisors######
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)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,K,S = IL()

for i in range(K):
  print(S,end=" ")
for i in range(N-K):
  if S != 10**9:
    print(S+1,end=" ")
  else:
    print(S-1,end=" ")

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>

using namespace std;
const long long MOD = 1000000007LL;

int main() {
    long long n, k; cin >> n >> k;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    long long ans = 0;
    for (int i = n-1; i >= 0; --i) {
        int num = 0;
        for (int j = n-1; j > i; --j) {
            if (a[i] > a[j]) {
                ++num;
            }
        }
        ans = (ans + num * k) % MOD;
    }
    for (int i = 0; i < n; ++i) {
        long long num = 0;
        for (int j = 0; j < n; ++j) {
            if (a[i] > a[j]) {
                ++num;
            }
        }
        ans = (ans + num * (k-1) * k / 2) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
a = list(map(int,input().split()))
a = np.array(a,dtype=np.int64)
point = 0
mod = 10**9+7

b = [((a>>i)&1).sum() for i in range(61)]
c = [n-b[i] for i in range(61)]
d = [c[i]*b[i]%mod for i in range(61)]

point = 0
for i in range(61):
    point += (2**i)*d[i]%mod

point %= mod

print(point)

Submission status: Runtime Error

Solution code:
N, K=map(int, input().split())
A=list(map(int, input().split()))
base=0
for i in range(N-1):
  for j in range(i+1:N):
    if A[i]>A[j]:
      base+=1
rep=K*(K+1)//2
ans=base*rep
print(ans)

Submission status: Runtime Error

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

mod = 10**9 + 7
result = 0
count = [0] * N
for a in A:
    count[a-1] += 1
    result += K * sum(count[a:])
    result %= mod

kn = 0
total = sum(count) % mod
for i in range(N):
    total -= count[i]
    kn += total
    kn %= mod

result += kn * K*(K-1)//2
result %= 10**9 + 7

print(result)

Submission status: Runtime Error

Solution code:
import streams, sequtils, strutils, algorithm, math, future, sets, tables, hashes
proc `ceilDiv`*[T](x, y: T): T = x div y + ord(x mod y != 0)
proc `//=`*(x: var SomeInteger; y: SomeInteger) = x = x div y
proc `%=`*(x: var SomeInteger; y: SomeInteger) = x = x mod y

var
    L = stdin.readLine.split.map(parseInt)
    N = L[0]
    K = L[1]
    A = stdin.readLine.split.map(parseInt)
    MOD = 10^9 + 7
    ans = 0.int64
    jun = newSeqWith(N, 0)
    inv = newSeqWith(N, 0)
for i in 0..N-1:
    for j in 0..N-1:
        if j < i:
            if A[i] < A[j]:
                jun[i] += 1
        else:
            if A[i] < A[j]:
                inv[i] += 1
for i in 0..N-1:
    ans += K * (((jun[i] * (K+1)) + (inv[i] * (K-1))) div 2)
    ans %= MOD
    # ans += (inv[i] * (K-1)) mod MOD
    # ans %= MOD
echo ans mod MOD

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a_list = list(map(int,input().split()))
a_list_2 = a_list + a_list
first_count = 0
p = 10** + 7
for i in range(1,n):
  if  a_list[i] < a_list[i-1]:
    first_count += 1
second_count = 0    
for a in range(1,2*n):
  if a_list[a] < a_list[a-1]:
    secount_count += 1
ans = first_count * k  + 1//2 * (k-1) * k * second_count
print(int(ans) % p)