output_description: Print the inversion number of B, modulo 10^9 + 7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N K
      A_0 A_1 ... A_{N - 1}
attempt: N, K = [int(_) for _ in input().split()]
  A = [int(_) for _ in input().split()]
  
  
  class BinaryIndexedTree:
      """
      Parameters
      ----------
      array : list
          to construct BIT from
      f : func
          binary operation of the abelian group
      fi : func
          inverse mapping of f
          i.e. f(a, b) == c <-> fi(c, a) == b
      e :
          identity element of the abelian group
      size : int
          limit for array size
      """
  
      def __init__(self, array, f, fi, e, size):
          self.f = f
          self.fi = fi
          self.e = e
          self.size = size
          self.n = len(array)
          self.dat = [e] * (size + 1)
          self.array = [e] * size
          self.build(array)
  
      def build(self, array_):
          for i, v in enumerate(array_):
              self.modify(i, v)
  
      def modify(self, p, v):
          """
          set value at position p (0-indexed)
          """
          self.add(p, self.fi(v, self.array[p]))
  
      def add(self, p, dv):
          """
          add value at position p (0-indexed)
          """
          fi, dat, f, size, array = self.fi, self.dat, self.f, self.size, self.array
          array[p] = f(array[p], dv)
          p += 1
          while p <= size:
              dat[p] = f(dat[p], dv)
              p += p & -p
  
      def query(self, l, r):
          """
          result on interval [l, r) (0-indexed)
          """
          return self.fi(self._query(r), self._query(l))
  
      def _query(self, p):
          dat, f, res = self.dat, self.f, self.e
          while p:
              res = f(res, dat[p])
              p -= p & -p
          return res
  
  
  f = lambda x, y: x + y
  fi = lambda z, x: z - x
  e = 0
  BIT = BinaryIndexedTree([0] * (N + 1), f=f, fi=fi, e=e, size=N + 1)
  ans1 = N * (N + 1) // 2
  for a in A:
      BIT.add(a, 1)
      ans1 -= BIT._query(a + 1)
  
  BIT = BinaryIndexedTree([0] * (2 * N + 1), f=f, fi=fi, e=e, size=2 * N + 1)
  ans2 = 2 * N * (2 * N + 1) // 2
  for a in A:
      BIT.add(a, 1)
      ans2 -= BIT._query(a + 1)
  for a in A:
      BIT.add(a, 1)
      ans2 -= BIT._query(a + 1)
  
  BIT = BinaryIndexedTree([0] * (3 * N + 1), f=f, fi=fi, e=e, size=3 * N + 1)
  ans3 = 3 * N * (3 * N + 1) // 2
  for a in A:
      BIT.add(a, 1)
      ans3 -= BIT._query(a + 1)
  for a in A:
      BIT.add(a, 1)
      ans3 -= BIT._query(a + 1)
  for a in A:
      BIT.add(a, 1)
      ans3 -= BIT._query(a + 1)
  
  x = ans1
  y = ans2
  z = ans3
  mod = 10**9 + 7
  K -= 1
  print((((K - 2) * (K - 1) * x - 2 * K * (K - 2) * y + (K - 1) * K * z) // 2) % mod)
  
problem_description: 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.
samples: [{"input": "2 2\n    2 1", "output": "3\n    \n\nIn this case, B~=~2,~1,~2,~1. We have:\n\n  * B_0 > B_1\n  * B_0 > B_3\n  * B_2 > B_3\n\nThus, the inversion number of B is 3.\n\n* * *"}, {"input": "3 5\n    1 1 1", "output": "0\n    \n\nA may contain multiple occurrences of the same number.\n\n* * *"}, {"input": "10 998244353\n    10 9 8 7 5 6 3 4 2 1", "output": "185297239\n    \n\nBe sure to print the output modulo 10^9 + 7."}]