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: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
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 MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
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

def main():
    N, K = MAP()
    A = LIST()
    count = 0
    for i in range(N):
        count_all = 0
        count_ = 0
        for j in range(N):
            if A[i] > A[j]:
                count_all += 1
                if i < j:
                    count_ += 1
        count += count_ * K % mod
        count += (count_all * ((K - 1) * K % mod) / 2) % mod
        count = count % mod
        # import pdb; pdb.set_trace()
    print(int(count) % mod)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


K_1 = Decimal(K)*Decimal(1+K) / Decimal(2)
K_1 %= Decimal(MOD)
K_2 = (K_1 - Decimal(K)) % Decimal(MOD)

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

res_prev = [0 for i in range(N)]

for i in range(N):
    a = As[i]
    for j in range(i):
        if a > As[j]:
            res_prev[i] += 1

ans = Decimal(0)

for i in range(N):
    ans += (Decimal(res_next[i]) * K_1) % Decimal(MOD)
    ans %= Decimal(MOD)
    ans += (Decimal(res_prev[i]) * K_2) % Decimal(MOD)
    ans %= Decimal(MOD)

print(int(ans))

Submission status: Wrong Answer

Solution code:
# kleene Inversion

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = 2
# k = 2
# a = [2, 1]

count_n = 0

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

count = count_n * ((1+k)*k//2)
print(count % (10**9+7))

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

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


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()
A = LIST()

B = []
for i in range(2):
    for a in A:
        B.append(a)
# print(B)
tenchi1 = bubble_sort(A)
tenchi2 = bubble_sort(B)

ni = tenchi2-2*tenchi1
# print(ni)

# tenchi = bubble_sort(A)
# print(tenchi)
# wa1 = 0.5 * (K) * (K+1)
wa2 = 0.5 * (K) * (K-1)
wa2 = int(wa2)
# ans1 = wa1 * tenchi1
# print("wa1", wa1)
# print("wa2", wa2)
# print("tenchi1", tenchi1)
# print("tenchi2", tenchi2)
# print("ni", ni)
ans1 = K*tenchi1
ans2 = wa2 * ni
ans = ans1 + ans2

ans = ans % mod
print(ans)
exit()

ans = ans % mod
print(ans)
exit()





print(wa)
ans = wa * tenchi
ans = ans % mod
print(ans)
# print(wa)
# ruikei = 0
# dp = [0] * (K+1)
# for i in range(1, K+1):
#     dp[i+1] = dp[i] + tenchi

# # print(ruikei)
# print(498245894647316481 % mod)



# dp = [0] * (K+1)
# dp[0] = tenchi

# for i in range(0, K):
#     dp[i+1] = dp[i] + tenchi
# # print(dp)
# print(dp[K])


# for i in range(K):
#     count + tenchi



# # print(B)
# for i in range(len(A)):
    # for j in range(i):
# count = 0
# for i in range(len(A)):
#     for j in range(i, len(A)):
#         if A[i] > A[j]:
#             count += 1
# print(count)

Submission status: Wrong Answer

Solution code:
import collections
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7
ans1=0
ans2=0
c=collections.Counter(A)
d=copy.deepcopy(c)
NN=0
while len(A)>0:
    x=A.pop(0)
    c[x]-=1
    for j in c:
        if x>j:
            ans1+=c[j]%mod
            NN+=d[j]%mod
ans1*=N
ans2=int(0.5*K*(K-1)*NN)%mod
ans=(ans1+ans2)%mod
print(ans)

Submission status: Wrong Answer

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

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

    count = 0
    count_ = 0
    for i,a in enumerate(A):
        for target in A[i+1:]:
            if int(a) > int(target):
                count += 1

        for target in A:
            if int(a) > int(target):
                count_ += 1

    C = count*K + count_*(K*K-(1+K)*K/2)
    print(int(C%1000000007)+count)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int, input().split()))
count = 0
for i in range(0,N-1):
    for j in range(i+1,N):
        if A[i] > A[j]:count += 1
count %= 1000000007
total = 0
for a in range(K+1):
    total += a
    total %= 1000000007
count = (count * total) % 1000000007
print(count)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().strip().split())
list = list(map(int, input().strip().split()))
s = 0
t = 0
k = k


for i in range(n):
    for j in range(i, n):
        if list[i] > list[j]:
            s += 1
            
list.reverse()           
for i in range(n):
    for j in range(i, n):
        if list[i] > list[j]:
            t += 1            
            
a = (k*(k+1)%1000000007)/2
b = (k*(k-1)%1000000007)/2

print(int((s*a+t*b)%1000000007))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
count = 0
for i in range(len(a)):
    for j in range(len(a)):
        if i <= j:
            break
        if a[i] < a[j]:
            count += 1
print(count)

a_count = len(a) * (len(a) - 1) // 2
print((count * k + (k * (k - 1) // 2 *a_count)) % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
from operator import itemgetter

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]

MOD = 10**9 + 7

array10=[0]*2001
is10=[0]*2001
AT=0
for i in range(N):
    a=int(A[i])
    is10[a]+=1
    AT+=array10[a]
    for j in range(a):
        array10[j]+=1

AT=AT%MOD
sum10=[i*j for i, j in zip(array10,is10)]
sum10=sum(sum10)
ans=int(AT*K)%MOD+int(sum10*(K*(K-1)/2))%MOD
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a0 = a[0]
an = a[n-1]
now = a0
c_self = 0
c_inter = 0
for i in range(n):
    for j in range(i,n):
        #print(i,j)
        #print("a",a[i],a[j])
        if a[i] > a[j]:
            c_self += 1
        if a[i] != a[j]:
            c_inter += 1
t =( (k-1) * k ) % (10**9 + 7)
l = (k * c_self) % (10**9 + 7)
q = (t * c_inter / 2) % (10**9 + 7)

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

Submission status: Wrong Answer

Solution code:
import math

def cul_sum(count,K):
	ans = 0
	for i in range(K+1):
		ans += i
	return ans

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

count_ans = 0

for i in range(len(A)):

	count = 0
	for j in range(i+1,len(A)):

		if A[i] > A[j]:
			count+=1
	if count != 0:
		count_ans = cul_sum(count,K)

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

x = 0
for l in range(N - 1):
  for r in range(l + 1, N):
    if A[l] > A[r]:
      x += 1
# print(x)
      
AA = A + A
y = 0
for l in range(2 * N - 1):
  for r in range(l + 1, 2 * N):
    if AA[l] > AA[r]:
      y += 1
y -= 2 * x
# print(y)
  
# print(int((K * x + K * (K - 1) * y / 2) % (10 ** 9 + 7)))
# print(int((K * x  % (10 ** 9 + 7) + K * (K - 1) * y / 2  % (10 ** 9 + 7)) % (10 ** 9 + 7)))
kkmod = (K * (K - 1)) % (10 ** 9 + 7)
Kxmod = (K * x) % (10 ** 9 + 7)
ans = (2 * Kxmod +  kkmod * y) % (10 ** 9 + 7)
print(int(ans / 2 % (10 ** 9 + 7)))

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
a = list(map(int,input().split()))
inner = int(0)
outer = int(0)
for i in range(0,n):
    for j in range(0,n):
        if a[i] > a[j]:
            outer += 1
            if i < j:
                inner += 1

b = (int(int(inner) * int(k)) + int(int(outer) * int(int(k) * int(k-1)) / 2))
print(int(int(b)%int(1000000007)))

Submission status: Wrong Answer

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

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

x = 0
for i in range(N):
    for j in range(N-1, i, -1):
        if A[j] < A[j-1]:
            A[j], A[j-1] = A[j-1], A[j]
            x += 1
M = 10**9 + 7
if x != 0:
    ans = ( ((K*x)%M) + ( ((1/4)*N*(N-1) % M) * (K*(K-1)%M) ) % M ) % (M)
    print(int(ans))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
def count_inversion(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
    return count
def cnt_bigger_elem(sequence):
    cnt = 0
    for i in range(N):
        for elem in sequence:
            if sequence[i] < elem:
                cnt += 1
    return cnt


#A = [1,2,3,5,4]

#print(cnt_bigger_elem(A))
#print(count_inversion(A))
BIG_NUM = 10**9+7
#ans0 = int((count_inversion(A) * K)%BIG_NUM + (K*(K-1)*cnt_bigger_elem(A)/2)%BIG_NUM)
#ans1 = int((count_inversion(A) * K)%BIG_NUM + ((K*(K-1)%(BIG_NUM))*cnt_bigger_elem(A))%BIG_NUM)
#ans2 = int(((count_inversion(A) * K) + (((((K%BIG_NUM)*((K-1)%BIG_NUM))/2)%BIG_NUM)*(cnt_bigger_elem(A)%BIG_NUM))))%BIG_NUM
#ans3= int(K*((K-1)*cnt_bigger_elem(A)/2)+count_inversion(A))%BIG_NUM
#ans2 = int((((count_inversion(A) * K)%BIG_NUM) + (((((K%BIG_NUM)*((K-1)%BIG_NUM))/2)%BIG_NUM)*(cnt_bigger_elem(A)%BIG_NUM))))%BIG_NUM
#print(ans2)## 惜しい
ans = int(((count_inversion(A)*K)%BIG_NUM + ((K*(K-1)/2)%BIG_NUM)*(cnt_bigger_elem(A)%BIG_NUM)%BIG_NUM)%BIG_NUM)
print(ans)

Submission status: Wrong Answer

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

MOD = 10 ** 9 + 7

X = 0

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

Y =0

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

print((X * K + int((K * (K-1))/2 * Y )) % MOD)

Submission status: Wrong Answer

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

MOD = 10**9 + 7

ansR = 0
ansL = 0

for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            if i > j:
                ansL += 1
            if i < j:
                ansR += 1


ans = ansR*((k+1)*k/2)%MOD + ansL*((k-1)*k/2)%MOD

print(int(ans%MOD))

Submission status: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
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 MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
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

def main():
    N, K = MAP()
    A = LIST()
    count = 0
    for i in range(N):
        count_all = 0
        count_ = 0
        for j in range(N):
            if A[i] > A[j]:
                count_all += 1
                if i < j:
                    count_ += 1
        count += count_ * K % mod
        count += (count_all * ((K - 1) * K % mod) / 2) % mod
        # import pdb; pdb.set_trace()
    print(int(count) % mod)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

r = 0
l = 0

for i in range(n):
    for ii in range(n):
        if i < ii and a[i] > a[ii]:
            r += 1
        if a[i] > a[ii]:
            l += 1

res = int((r*k + (l*((k-1)*k)/2)) % (10**9+7))

print(res)

Submission status: Wrong Answer

Solution code:
import math

def cul_sum(count,K):
	ans = 0
	for i in range(K+1):
		ans += i
	return ans

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

count_ans = 0

for i in range(len(A)):
	print('i:',A[i])
	count = 0
	for j in range(i+1,len(A)):
		print('j:',A[j])
		if A[i] > A[j]:
			count+=1
	if count != 0:
		count_ans = cul_sum(count,K)

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

Submission status: Wrong Answer

Solution code:
import math

N, K = map(int, input().split())
A = list(map(int, input().split()))
inv = 0
for i in range(N):
    for j in range(i+1, N):
        if A[i]>A[j]:
            inv+=1
ans = 1
a = 10**9+7
for i in range(1, K+1):
    ans = (ans*i)%a

ans = ans*inv
print(ans)

Submission status: Wrong Answer

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

def count_inversion(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
    return count

def count_inversion_B(sequence):
    count = 0
    for a in A:
        count = count + (A.count(a) - 1)
    return count

def count_inversion_C(sequence):
    count_hairetu = []
    for a in A:
        count_hairetu.append(A.count(a))
    return count_hairetu

count_inv = count_inversion(A)
count_tyouhuku = count_inversion_B(A)
count_hairetu = count_inversion_C(A)

count_a = 0
for i in range(len(count_hairetu)):
    count_a = count_tyouhuku * count_hairetu[i]

count_sum = (count_inv * K) + (count_a * (K-1))

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

Submission status: Wrong Answer

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

for i in range(n):
	for j in range(n):
		if a[i] > a[j] and i != j:
			cnt2 += 1
#print((int((k*(k-1)/2*cnt2)%(10**9+7))+(k*cnt1)%(10**9+7))%(10**9+7))
print(int((k*cnt1+(k-1)*k/2*cnt2)%(10**9+7)))

Submission status: Wrong Answer

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

a=list(map(int,input().split()))
tentou1=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      tentou1+=1
a.sort()
a.reverse()
stentou=0
for i in range(len(a)):
  for j in range(i+1,len(a)):
    if(a[i]>a[j]):
      stentou+=1
answer=int(tentou1*K + int(stentou*K*(K-1)/2))
print(answer%1000000007)

Submission status: Wrong Answer

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

r = 0
l = 0

for i in range(n):
    for ii in range(n):
        if i < ii and a[i] > a[ii]:
            r += 1
        if a[i] > a[ii]:
            l += 1

print(l,r,k)

res = int((r*k + (l*((k-1)*k)/2)) % (10**9+7))

print(res)
print(185297239-res)

Submission status: Wrong Answer

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

c1=0
c2=0
for i,a in enumerate(a_list):
    l=[x for x in a_list[i+1:] if a>x]
    c1+=len(l)
    l=[x for x in a_list if a>x]
    c2+=len(l)
k1_sum=K*(K+1)/2
k2_sum=K*(K+1)*(K+2)/6
print(int((c1*K+c2*k1_sum-c2*K)%(10**9+7)))

Submission status: Wrong Answer

Solution code:
mod=1000000007
N,K= (int(i) for i in input().split()) 
A = [int(i) for i in input().split()] 
B=[]
C=[0]*N
D=[0]*N
ans=0
for i in range(N):
    B.append(A[i])
for i in range(N):
    B.append(A[i])
    
for i in range(N):
    for j in range(i+1,i+N):
        if B[i]>B[j]:
            C[i-N]+=1
for i in range(N):
    for j in range(i,N):
        if A[i]>A[j]:
            D[i]+=1
for i in range(N):
    ans+=int((2*D[i]+(K-1)*C[i])*K/2)
print(int(ans)%mod)

Submission status: Wrong Answer

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 = (B + np.sum(D < A[i]) % (10**9 + 7)) % (10**9 + 7)
    C = (C + np.sum(A < A[i]) % (10**9 + 7)) % (10**9 + 7)
    

E = B * K % (10**9 + 7)

F = C * (int((K-1) * K/2) % (10**9 + 7)) % (10**9 + 7)

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
from operator import itemgetter

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]

MOD = 10**9 + 7

array10=[0]*2001
is10=[0]*2001
AT=0
for i in range(N):
    a=int(A[i])
    is10[a]=1
    AT+=array10[a]
    for j in range(a):
        array10[j]+=1

AT=AT%MOD
sum10=[i*j for i, j in zip(array10,is10)]
sum10=sum(sum10)

ans=int(AT*K)%MOD+int(sum10*(K*(K-1)/2))%MOD
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
#10^9+7  で割った余り
k = k %(1000000000 + 7)
#その文字より前に大きな数字
before_cnt = 0
#その文字より後に大きな数字
after_cnt = 0
n_list = list(map(int, input().split()))
for i in range(n-1):
  for j in range(i, n):
    if n_list[i] > n_list[j]:
      after_cnt+=1
    elif n_list[i] < n_list[j]:
      #print("i",i,"j",j)
      before_cnt+=1
      '''
      if i < j:
        after_cnt+=1
      else:
        before_cnt+=1
'''
kurikaesi = int(((1 + k)*k/2)%(1000000000+7))
#print("type",type(k),"kurikaesi",kurikaesi)
#print(after_cnt, before_cnt)
print((before_cnt*(kurikaesi-k) + after_cnt*kurikaesi)%(1000000000+7))

Submission status: Wrong Answer

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

c=0
for k in range(K, 0, -1):
  for i in range(N):
    for j in range(i,N):
      if l[i] > l[j]:
        c += 1
  c *= k
c = c % (10*9+7)
print(c)

Submission status: Wrong Answer

Solution code:
N, K = [int(i) for i in input().split(" ")]
A_list = [int(i) for i in input().split(" ")]
B_list = [0]*N
s = sA = 0
K = ((K)*(K+1)//2)
for n in range(N):
    a0 = A_list[n]
    for a in A_list[n+1:]:
        if a0 > a:
            B_list[n]+= 1
for b in B_list:
    s+= (b * K) % (10**9 + 7)
print(s )

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
def count_inversion(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
    return count
def cnt_bigger_elem(sequence):
    cnt = 0
    for i in range(N):
        for elem in sequence:
            if sequence[i] < elem:
                cnt += 1
    return cnt


#A = [1,2,3,5,4]

#print(cnt_bigger_elem(A))
#print(count_inversion(A))
BIG_NUM = 10**9+7
#ans0 = int((count_inversion(A) * K)%BIG_NUM + (K*(K-1)*cnt_bigger_elem(A)/2)%BIG_NUM)
#ans1 = int((count_inversion(A) * K)%BIG_NUM + ((K*(K-1)%(BIG_NUM))*cnt_bigger_elem(A))%BIG_NUM)
#ans2 = int(((count_inversion(A) * K) + (((((K%BIG_NUM)*((K-1)%BIG_NUM))/2)%BIG_NUM)*(cnt_bigger_elem(A)%BIG_NUM))))%BIG_NUM
#ans3= int(K*((K-1)*cnt_bigger_elem(A)/2)+count_inversion(A))%BIG_NUM
#ans2 = int((((count_inversion(A) * K)%BIG_NUM) + (((((K%BIG_NUM)*((K-1)%BIG_NUM))/2)%BIG_NUM)*(cnt_bigger_elem(A)%BIG_NUM))))%BIG_NUM
#print(ans2)## 惜しい
ans = int(((count_inversion(A)*K)%BIG_NUM + ((K*(K-1)/2)%BIG_NUM)*cnt_bigger_elem(A)%BIG_NUM)%BIG_NUM)
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))*2
count1=0
count2=0
for i in range(2*n):
  for j in range(i+1,2*n):
    if a[i]>a[j] and j<n:
      count1+=1
      count2+=1
    elif a[i]>a[j]:
      count2+=1

if k==1:
  print(count1%(10**9+7))
else:
  ans=((count2-2*count1)*k*(k-1)/2+count1*k)%(10**9+7)
  print(int(ans)+count1)

Submission status: Wrong Answer

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

for i in range(n):
	for j in range(n):
		if a[i] > a[j] and i != j:
			cnt2 += 1
print((int((k*(k-1)/2*cnt2)%(10**9+7))+(k*cnt1)%(10**9+7))%(10**9+7))

Submission status: Wrong Answer

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

x = 0
for l in range(N - 1):
  for r in range(l + 1, N):
    if A[l] > A[r]:
      x += 1
# print(x)
      
AA = A + A
y = 0
for l in range(2 * N - 1):
  for r in range(l + 1, 2 * N):
    if AA[l] > AA[r]:
      y += 1
y -= 2 * x
# print(y)
  
# print(int((K * x + K * (K - 1) * y / 2) % (10 ** 9 + 7)))
# print(int((K * x  % (10 ** 9 + 7) + K * (K - 1) * y / 2  % (10 ** 9 + 7)) % (10 ** 9 + 7)))
kkmod = (K * (K - 1)) % (10 ** 9 + 7)
Kxmod = (K * x) % (10 ** 9 + 7)
ans = (Kxmod + 1 / 2 * kkmod * y) % (10 ** 9 + 7)
print(int(ans))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 24 21:32:07 2019

@author: kato yugo
"""

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

a = [0 for i in range(n+1)]

for i in range(n):
    a[i] = int(a_li[i])
a[n] = 10**10   
 
ans_memo = [0 for i in range(n)]   
for i in range(n):
    for j in range(i+1,n+1):
        if a[i]>a[j]:
            ans_memo[i] += 1

ans = 0

for i in range(n):
    q = ans_memo[i]
    ans += (q*k)%mod
    
a2 = a
a3 = sorted(a2,reverse=True)

qqq = 0
memo2 = 1
for i in range(1,n):
    if a3[i] > a3[i+1]:
        qqq += memo2*(n-i)
        memo2 = 1
    else:
        memo2 += 1
    
total = int((k*(k-1))/2)%mod
ans += qqq*total

print(ans%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))
num = [[0, 0] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            num[i][1] += 1
        if (i < j) and (a[i] > a[j]):
            num[i][0] += 1
num_np = np.array(num)
ks = k * (k - 1) / 2 % 1000000007
sum_left = sum(num_np[:,0])
sum_right = sum(num_np[:,1])
output = (sum_left * k) % 1000000007 + (sum_right * int(ks)) % 1000000007
print(output % 1000000007)

Submission status: Wrong Answer

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

def cal(A, N):
    cnt1 = 0
    cnt2 = 0
    for i in range(N):
        for j in range(i+1,N):
            if A[N-1-j] > A[N-1-i]:
                cnt1 += 1
    for i in range(N):
        for j in range(N):
            if A[N-1-i] < A[j]:
                cnt2 += 1
    
    return cnt1, cnt2
    
    
x, y = cal(A,N)

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

mod = 10**9+7

g = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        elif i >= j:
            continue
        if a[i] > a[j]:
            #print(i,j)
            g += 1

if k == 1:
    print(g)
    exit()
    
a2 = []

for i in range(2*n):
    a2.append(a[i%n])
    
f = 0

for i in range(n):
    for j in range(2*n):
        if i == j:
            continue
        elif i >= j:
            continue
        if a2[i] > a2[j]:
            #print(i,j)
            f += 1

t = (f-g)%mod

#print(t)
#exit()
#print(int((k*g%mod + t*(0.5*((k-1)*k))%mod)%mod))
print(int(( (k%mod*g%mod)%mod + (t*(0.5*((k-1)%mod*k%mod)) ) %mod)%mod))
exit()

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
li = list(map(int,input().split()))
mod = 10**9 +7
 
ans_1 = 0
ans_2 = 0
for i in range(n-1):
  for j in range(i+1,n):
    if li[i] > li[j]:
      ans_1+= 1
for i in range(n):
  for j in range(n):
    if li[i] < li[j]:
      ans_2 += 1
ans = k*ans_1%mod + 0.5*k*(k-1)%mod*ans_2%mod
print(int(ans%mod))

Submission status: Wrong Answer

Solution code:
import math

def cul_sum(count,K):
	ans = 0
	for i in range(K+1):
		ans += i
	return ans

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

count_ans = 0

for i in range(len(A)):
	count = 0
	for j in range(i,len(A)):
		if A[i] > A[j]:
			count+=1
	if count != 0:
		count_ans = cul_sum(count,K)

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

Submission status: Wrong Answer

Solution code:
#######################################
prime = 10**9+7

def sowa(num):
  return int((1+num)*num/2)
#######################################
n,k = map(int, input().split())
a = list(map(int, input().split()))

if n*k<100000:
  b = a*k
  tento0 = [sum([1 if b[i]>b[j] else 0 for j in range(i+1, len(b))]) for i in range(len(b))]
  print(sum(tento0)%prime)
else:
  tento1 = [sum([1 if a[i]>a[j] else 0 for j in range(i+1,n)]) for i in range(n-1)]
  tento2 = [sum([1 if a[i]>a[j] else 0 for j in range(n)]) for i in range(n)]
  ret = (sum(tento1) *k %prime) + (sum(tento2) *(sowa(k-1) %prime) %prime)
  print(ret%prime)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
from operator import itemgetter

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]

MOD = 10**9 + 7

array10=[0]*2001
is10=[0]*2001
AT=0
for i in range(N):
    a=int(A[i])
    is10[a]=1
    AT+=array10[a]
    for j in range(a):
        array10[j]+=1

AT=AT%MOD
sum10=[i*j for i, j in zip(array10,is10)]
sum10=sum(sum10)

ans=int(AT*K)%MOD+int(sum10*(K*(K-1)/2))%MOD
print(ans)

Submission status: Wrong Answer

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

def count_inversion(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
    return count

def count_inversion_B(sequence):
    count = 0
    for a in A:
        count = count + (A.count(a) - 1)
    return count

def count_inversion_C(sequence):
    count_hairetu = []
    for a in A:
        count_hairetu.append(A.count(a))
    return count_hairetu

count_inv = count_inversion(A)
count_tyouhuku = count_inversion_B(A)
count_hairetu = count_inversion_C(A)

count_sum = (count_inv * K) + (count_tyouhuku * (K-1))

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#######################################
prime = 10**9+7

def sowa(num):
  return int((1+num)*num/2)
#######################################
n,k = map(int, input().split())
a = list(map(int, input().split()))

if n*k<1000:
  b = a*k
  tento0 = [sum([1 if b[i]>b[j] else 0 for j in range(i+1, len(b))]) for i in range(len(b))]
  print(sum(tento0)%prime)
else:
  tento1 = [sum([1 if a[i]>a[j] else 0 for j in range(i+1,n)]) for i in range(n-1)]
  tento2 = [sum([1 if a[i]>a[j] else 0 for j in range(n)]) for i in range(n)]
  ret = (sum(tento1) *k %prime) + (sum(tento2) *(sowa(k-1) %prime) %prime)
  print(ret%prime)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
from operator import itemgetter

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]

MOD = 10**9 + 7

array10=[0]*2001
is10=[0]*2001
AT=0
for i in range(N):
    a=int(A[i])
    is10[a]=1
    AT+=array10[a]
    for j in range(a):
        array10[j]+=1
print(AT)
AT=AT%MOD
sum10=[i*j for i, j in zip(array10,is10)]
sum10=sum(sum10)
print(sum10)
ans=int(AT*K)%MOD+int(sum10*(K*(K-1)/2))%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
N,kk=map(int,input().split())
l=list(map(int,input().split()))
cnt=0
cntt=0
p=10**9+7
K=kk%p
for i in range(N):
	for j in range(N):
		if l[i]>l[j] and j>i:
			cnt+=1
for k in range(N):
	for m in range(N):
		if l[k]>l[m] and k>m:
			cntt+=1
Cn=cntt*int((K-1)*K/2)+int(K*(K+1)/2)*cnt+cnt
print(Cn%p)

Submission status: Wrong Answer

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


K_1 = Decimal(K)*Decimal(1+K)% Decimal(MOD)
K_1 /= Decimal(2)
K_2 = (K_1 - Decimal(K)) % Decimal(MOD)

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

res_prev = [0 for i in range(N)]

for i in range(N):
    a = As[i]
    for j in range(i):
        if a > As[j]:
            res_prev[i] += 1

ans = Decimal(0)
for i in range(N):
    ans += (Decimal(res_next[i]) * K_1) % Decimal(MOD)
    ans += (Decimal(res_prev[i]) * K_2) % Decimal(MOD)
    ans %= Decimal(MOD)

print(int(ans))