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:
INF = 10 ** 9 + 7

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

# 単体のA内で発生するケース
inv = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[i+1]:
            inv += 1
inv = inv * K

# 異なるA間で発生するケース
ini = 0
for k in range(N-1):
    for l in range(k+1, N):
        if A[k] > A[l]:
            ini += 1
ini = ini * K * (K-1) / 2
ans = (inv+ini) % INF
print(int(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    MOD = 10 ** 9 + 7
    #転倒数、Aの中で
    C1 = np.array([0] * n)
    C2 = np.array([0] * n)
    for i in range(n):
        C1[i] = np.count_nonzero(A[i:] < A[i])
        C2[i] = np.count_nonzero(A < A[i])

    C2 = C2 - C1
    #print(C1,C2)

    ans = 0
    for i in range(n):
        ans += (C1[i] * (k + 1) * k // 2 + C2[i] * k * (k - 1) // 2) % MOD
        

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
import math
from fractions import Fraction
import itertools

input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[0]*n
q=[0]*n
ans=0
mod=10**9+7
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            if i>j:
                p[i]+=1
            elif i<j:
                q[i]+=1
                
for i in range(n):
    ans+=(k*q[i]+((p[i]+q[i])*k*(k-1)/2)%mod)%mod
    ans=ans%mod
print(int(ans%mod))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
mod = 10**9+7
a = 0
for i in range(n):
  b = l[i]
  t = (len([1 for m in l if  m<b])%mod)*(int( (k-1)%mod*k/2)%mod)%mod
 # print(i,b,t)
  s = (len([1 for m in l[i:] if m<b])%mod)*k%mod
#  print(s)
  a += (s+t)%mod
print(a%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
mod = 10**9+7
a = 0
for i in range(n):
  b = l[i]
  t = (len([1 for m in l if  m<b])%mod)*(int((k-1)%mod*k/2))%mod
 # print(i,b,t)
  s = (len([1 for m in l[i:] if m<b])%mod)*k%mod
#  print(s)
  a += int(s+t)%mod
print(a%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
mod = 10**9+7
a = 0
for i in range(n):
  b = l[i]
  t = (len([1 for m in l if  m<b])%mod)*((k-1)%mod*k/2)%mod
 # print(i,b,t)
  s = (len([1 for m in l[i:] if  m<b])%mod)*k%mod
#  print(s)
  a += int(s+t)%mod
print(a%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
mod = 10**9+7
a = 0
for i in range(n):
  b = l[i]
  t = (len([1 for m in l if  m<b])%mod)*((k-1)*k/2)%mod
 # print(i,b,t)
  s = (len([1 for m in l[i:] if  m<b])%mod)*k%mod
#  print(s)
  a += int(s+t)%mod
print(a%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
l = list(map(int,input().split()))
mod = 10**9+7
a = 0
l1 = sorted(l)
for i in l:
  t = l1.index(i)
  a += t*(k-1)*k/2
 # print(t,a)
  s = l.index(i)
  a += len([1 for e in l[s:] if e<i])*k
#  print(s,a)
print(int(a)%mod)

Submission status: Wrong Answer

Solution code:
N,K=(int(x) for x in input().split())
A=list(map(int,input().split()))
syoko=[0]*N
kosa=[0]*N
for n in range(N):
    for l in range(N):
        if A[n]>A[l]:
            kosa[n]+=1
for n in range(N):
    for l in range(n,N):
        if A[n]>A[l]:
            syoko[n]+=1
count=0
for n in range(N):
    b=(K-1)*kosa[n]%(10**9+7)
    c=K*(syoko[n]+b/2)%(10**9+7)
    count=(count+c)%(10**9+7)
print(round(count%(10**9+7)))

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
n, k, *a = map(int, open(0).read().split())
s = 0
for i in range(n):
  s += sum(j>i and a[j]<a[i] for j in range(n))
t = 0
for i in range(n):
  t += sum(a[j]<a[i] for j in range(n))
print((s*n + k*~-k//2*t) % MOD)

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()


    total = 0
    for i in range(n):
        for j in range(n):
            if a[i] < a[j]:
                total+=1
                total%=MOD

    ans = total*(k*(k-1)//2) % MOD

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

    res = (ans + (cnt * k) % MOD) % MOD

    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()


    total = 0
    for i in range(n):
        for j in range(n):
            if a[i] < a[j]:
                total+=1
                total%=MOD

    ans = total*(k*(k-1)//2) % MOD

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

    res = (ans + (cnt * k) % MOD) % MOD

    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()


    total = 0
    for i in range(n):
        for j in range(n):
            if a[i] < a[j]:
                total+=1
                total%=MOD

    ans = total*((k*(k-1)//2) % MOD) % MOD

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

    res = (ans + (cnt * k) % MOD) % MOD

    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()
    c = collections.Counter(a)

    d = {i: 0 for i in a}

    total = 0
    for ck, cv in c.items():
        for dk, dv in d.items():
            if ck > dk:
                total += cv
                total %= MOD

    ans = total*((k*(k-1)//2) % MOD) % MOD

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

    res = (ans + (cnt * k) % MOD) % MOD

    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()
    c = collections.Counter(a)

    d = {i: 0 for i in a}

    total = 0
    for ck, cv in c.items():
        for dk, dv in d.items():
            if ck > dk:
                total += cv

    ans = total*(k*(k-1)//2)

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

    res = (ans + (cnt * k) % MOD) % MOD

    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()
    c = collections.Counter(a)

    d = {i: 0 for i in a}

    total = 0
    for ck, cv in c.items():
        for dk, dv in d.items():
            if ck > dk:
                total += cv

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

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

    res = (ans + (cnt * k) % MOD) % MOD

    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()
    c = collections.Counter(a)

    d = {i: 0 for i in a}

    tmp = 0
    for ck, cv in c.items():
        for dk, dv in d.items():
            if ck > dk:
                d[dk] += cv

    ans = 0
    for dk, dv in d.items():
        ans += ((k - 1) * (2 * dv + (k - 2) * dv) // 2) % MOD
        ans %= MOD

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

    res = (ans + (cnt * k) % MOD) % MOD

    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

# count inv in A
cnt = 0
for i in range(N):
    for j in range(i, N):
        if A[i] > A[j]:
            cnt += 1

cmb_cnt = 0
for a in A:
   cmb_cnt += len([x for x in A if x < a]) 

kC2 = (K*(K-1))//2
ans = (cnt*K)+(cmb_cnt*kC2)
print(cnt)
print(cmb_cnt)
print(ans%(10**9+7))

Submission status: Wrong Answer

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

sum=0
for i in range(N):
    for j in range(N):
        if A[i]>A[j] and i>j:
            sum+=math.factorial(K-1)
        if A[i]>A[j] and i<j:
            sum+=math.factorial(K)
print(sum % (10**9+7))

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict, deque, Counter
import sys
from bisect import bisect_left
import heapq
import math

sys.setrecursionlimit(1000000000)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
n,k = map(int, stdin.readline().rstrip().split())
#S = [list(stdin.buffer.readline().decode().rstrip()) for _ in range(h)]
A = list(map(int, stdin.readline().rstrip().split()))

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

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

a_inten = a_inten - a_tento

print(int((a_tento*(k*(k+1)/2)+ a_inten*((k*(k-1)/2)))  %MOD))

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict, deque, Counter
import sys
from bisect import bisect_left
import heapq
import math

sys.setrecursionlimit(1000000000)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
n,k = map(int, stdin.readline().rstrip().split())
#S = [list(stdin.buffer.readline().decode().rstrip()) for _ in range(h)]
A = list(map(int, stdin.readline().rstrip().split()))

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

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

a_inten = a_inten - a_tento
print(a_inten)

print(int((a_tento*(k*(k+1)/2)+ a_inten*((k*(k-1)/2)))  %MOD))

Submission status: Wrong Answer

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

A=[int(N) for N in A]

prev=0
foll=0
for i in range(N):
    print('Ai',A[i])
    for j in range(i):
        if A[i]>A[j]:
            prev+=1
    for j in range(i,N):
        if A[i]>A[j]:
            foll+=1
    print(foll)

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

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
MOD = 10 ** 9 + 7
sm1 = [0] * n
sm2 = [0] * n
for i in range(n):
    now = a[i]
    for j in range(i+1,n):
        if now > a[j]:
            sm1[i] += 1
for i in range(n):
    now = a[i]
    for j in range(i):
        if now > a[j]:
            sm2[i] += 1
a1 = sum(sm1) % MOD
d = (sum(sm2) + a1) % MOD

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

Submission status: Wrong Answer

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

cnt = [0] * (n)

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

total = sum(cnt)
total %= mod

ans = 0

ans = total * k
ans %= mod
ans *= k + 1
ans %= mod
ans //= 2
ans %= mod

print(ans)

Submission status: Wrong Answer

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

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

y = 0
for a1 in a:
    for a2 in a:
        print(a1,a2)
        if a1 > a2: y += 1

ans = (cnt * k + y * k * (k-1)//2)%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 1000000007

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

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

fir = [0]*n

for i in range(n-1):
    for j in range(i+1,n):
        if t[i] > t[j]:
            fir[i] += 1    

sec = [0]*n

for i in range(n-1):
    for j in range(n):
        if t[i] > t[j]:
            sec[i] += 1

ans = 0

for i in range(n):
    ans += fir[i]*k+sec[i]*k*(k-1)//2
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:

SOSU = (10**9 + 7)

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

#print(A)

cntall = 0
cntusiro = 0

for indexi, i in enumerate(A):
    for indexj, j in enumerate(A):
        if i > j :
            cntall += 1
            if indexi < indexj:
                cntusiro += 1
        #print("roop:",i,j,indexi,indexj,cntall,cntusiro)

anst = (k*(k -1))*cntall/2 + k * cntusiro 


ans = anst % SOSU

#print ( cntall, cntusiro)
print(int(ans) )

Submission status: Wrong Answer

Solution code:

SOSU = (10**9 + 7)

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

#print(A)

cntall = 0
cntusiro = 0

for indexi, i in enumerate(A):
    for indexj, j in enumerate(A):
        if i > j :
            cntall += 1
            if indexi < indexj:
                cntusiro += 1

anst = (k*(k -1))*cntall/2 + k * cntusiro 


ans = anst % SOSU

print(int(ans))

Submission status: Wrong Answer

Solution code:

SOSU = (10**9 + 7)

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

#print(A)
# [7, 9, 7, 5]

#A = A * 500

cntall = 0
cntusiro = 0

for indexi, i in enumerate(A):
    for indexj, j in enumerate(A):
        if i > j :
            cntall += 1
            if indexi < indexj:
                cntusiro += 1

anst = (k*(k -1))*cntall/2 + k * cntusiro 


ans = anst % SOSU

print( ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
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

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n - 1):
    cnt = 0
    for j in range(i + 1, n):
        if a[i] > a[j]:
            cnt += 1
    ans += cnt
ans *= (k + 1) * k // 2
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
ans=0

# BIT Binary indexed tree
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

# BIT 転倒数　bubble sort
bit = Bit(max(A)+1)
ans = 0
for i, a in enumerate(A):
    ans += i - bit.sum(a+1)
    bit.add(a, 1)

tmp=ans*k%MOD+k*(k-1)//2*ans%MOD
tmp%=MOD
print(tmp)

Submission status: Wrong Answer

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

gen=10**9+7

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

nn=len(set(a))
      
print((k*count+nn*(nn-1)*k*(k-1)//4)%gen)

Submission status: Wrong Answer

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

gen=10**9+7

count=0
for i in range(n):
  for j in range(i+1,n):
    if a[i]>a[j]:
      count+=1
      
print((k*count+n*(n-1)*k*(k-1)//4)%gen)

Submission status: Wrong Answer

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

for i in range(N - 1):
    for j in range(i + 1, 2 * N):
        if j == N:
            c = b
        if A[i] > A[j] and j < N:
            b += 1
        elif A[i] > A[j] and j >= N:
            c += 1
    if b == c - b:
        ans += b * K * (K + 1) // 2
    else:
        ans += b * K + (c - b) * K * (K - 1) // 2
    b = 0
    c = 0

print(ans % mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import collections
N,K = map(int,input().split())
A = list(map(int, input().split()))
Ni_block = 0
bignum = pow(10,9)+7
for i in range(N):
   for j in range(i+1,N):
      if A[i]>A[j]:
         Ni_block+=1
c = collections.Counter(A)
N_multiple = 1
# print(c)
for i in c:
   # print(i, c[i])
   N_multiple*=c[i]
   
# print(N_multiple)
# print(len(c))
Ndiff = len(c)
Ni = Ni_block*K+(((K*(K-1))//2) % bignum)*(((Ndiff*(Ndiff-1))//2) % bignum)*(N_multiple%bignum)
print(Ni%bignum)

Submission status: Wrong Answer

Solution code:
import collections
N,K = map(int,input().split())
A = list(map(int, input().split()))
Ni_block = 0
bignum = pow(10,9)+7
for i in range(N):
   for j in range(i+1,N):
      if A[i]>A[j]:
         Ni_block+=1
c = collections.Counter(A)
# print(Ni_block)
# print(len(c))
Ndiff = len(c)
Ni = Ni_block*K+(((K*(K-1))//2) % bignum)*(((Ndiff*(Ndiff-1))//2) % bignum)
print(Ni%bignum)

Submission status: Wrong Answer

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

ans1 = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            ans1 += 1
ans2 = 0
for i in range(N):
    for j in range(N):
        if Aso[i] > Aso[j]:
            ans2 += 1
ans1 %= 10**9 + 7
ans2 %= 10**9 + 7


ans = int(ans1 * K % (10**9 + 7) + ans2 * (1 + K-1)*(K-1)/2 % (10**9 + 7))

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

Submission status: Wrong Answer

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

ans1 = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            ans1 += 1
ans2 = 0
for i in range(N):
    for j in range(N):
        if Aso[i] > Aso[j]:
            ans2 += 1

ans = int(ans1 * K % (10**9 + 7) + ans2 * (1 + K-1)*(K-1)/2 % (10**9 + 7))

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

Submission status: Wrong Answer

Solution code:
import sys

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


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    C = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if A[i] > A[j]:
                C[i] += 1

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

    res = 0
    for c in C:
        res += (2 * c + (k - 1) * c) * k // 2
        res %= mod

    for d in D:
        res += (2 * d + (k - 2) * d) * (k - 1) // 2
        res %= mod
    print(res)



if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

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

ans1 = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            ans1 += 1
ans2 = 0
for i in range(N-1):
    for j in range(i+1, N):
        if Aso[i] == Aso[j]:
            continue
        ans2 += 1

ans = int(ans1 * K + ans2 * (1 + K-1)*(K-1)/2)

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

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
mod = 10 ** 9 + 7
for i in range(N):
    #print(cnt)
    for j in range(N):
        if a[i] > a[j]:
            cnt += 1
ans = cnt * ((K - 1) * K) % mod * 500000004 % mod
for i in range(N - 1):
    for j in range(i + 1, N):
        if a[i] > a[j]:
            ans += K % mod
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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